CSES - Network Breakdown | Sự cố Mạng lưới
Xem PDFMạng lưới của Syrjälä có \(n\) máy tính và \(m\) kết nối giữa chúng. Mạng lưới gồm các thành phần các máy tính có thể gửi tin nhắn cho nhau.
Không ai ở Syrjälä biết cách mạng lưới hoạt động. Vì lý do này, nếu một kết nối gặp sự cố, sẽ không ai sửa nó. Trong tình huống này, một thành phần có thể bị chia thành hai thành phần.
Nhiệm vụ của bạn là tính số lượng thành phần sau mỗi sự cố kết nối.
Input
Dòng đầu tiên là ba số nguyên \(n, m\) và \(k\) : số lượng máy tính, kết nối và sự cố. Các máy tính được đánh số \(1,2,...,n\).
Tiếp theo là \(m\) dòng mô tả các kết nối. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : có một kết nối giữa hai máy \(a\) và \(b\). Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy.
Cuối cùng là \(k\) dòng mô tả các sự cố. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : kết nối giữa hai máy \(a\) và \(b\) gặp sự cố.
Output
Sau mỗi sự cố, in ra số lượng thành phần.
Giới hạn
- \(1 \le n \le 10^5\)
- \(1 \le m \le 2 \cdot 10^5\)
- \(1 \le k \le m\)
- \(1 \le a,b \le n\)
Ví dụ
Input
5 5 3
1 2
1 3
2 3
3 4
4 5
3 4
2 3
4 5
Output
2 2 3
Bình luận
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
define MASK(i) (1LL << (i))
define GETBIT(mask, i) (((mask) >> (i)) & 1)
define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, char separator = ' ', char finish = '\n'){
for(auto item: container) cout << item << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
struct DSU{
long n;
vector<long> parent, sz;
DSU(long _n){
n = _n;
parent.resize(n+1); sz.resize(n+1, 1);
for(long i = 1; i<=n; ++i) parent[i] = i;
}
long find_set(long u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));}
bool same_set(long u, long v){return find_set(u) == find_set(v);}
bool join_set(long u, long v){
u = find_set(u), v = find_set(v);
if (u != v){
if (sz[u] < sz[v]) swap(u, v);
parent[v] = u;
sz[u] += sz[v];
return true;
}
return false;
}
};
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
long n, m, k; cin >> n >> m >> k;
set<pair\<long, long>> edges;
for(long i = 0; i<m; ++i){ long u, v; cin >> u >> v;
if (u > v) swap(u, v);
edges.insert({u, v});
}
vector<pair\<long, long>> autism;
for(long i = 0; i<k; ++i){ long u, v; cin >> u >> v;
if (u > v) swap(u, v);
autism.push_back({u, v});
edges.erase({u, v});
}
reverse(ALL(autism));
DSU mst(n);
long ans = n;
for(auto item: edges) ans -= mst.join_set(item.first, item.second);
vector<long> res;
for(auto item: autism){
res.push_back(ans);
ans -= mst.join_set(item.first, item.second);
}
reverse(ALL(res));
printArr(res);
return 0;
}
1 bình luận nữa