Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int maxn = 1e5 + 10;
- int idx[maxn];
- int sz[maxn];
- void init() {
- for(int i = 0; i < maxn; i++) {
- idx[i] = i;
- sz[i] = 1;
- }
- }
- int find_root(int x) {
- while(x != idx[x]) {
- idx[x] = idx[idx[x]];
- x = idx[x];
- }
- return x;
- }
- bool check(int A, int B) {
- return find_root(A) == find_root(B);
- }
- void unite(int A, int B) {
- int rootA = find_root(A);
- int rootB = find_root(B);
- if(rootA != rootB) {
- if(sz[rootA] < sz[rootB]) {
- sz[rootB] += sz[rootA];
- idx[rootA] = idx[rootB];
- }
- else {
- sz[rootA] += sz[rootB];
- idx[rootB] = idx[rootA];
- }
- }
- }
- vector<int> danger_graph[maxn];
- vector<int> safe_graph[maxn];
- int main() {
- init();
- int n;
- cin >> n;
- int o;
- cin >> o;
- for(int i = 0; i < o; i++) {
- int a, b;
- cin >> a >> b;
- a--; b--;
- danger_graph[a].push_back(b);
- danger_graph[b].push_back(a);
- unite(a, b);
- }
- int s;
- cin >> s;
- for(int i = 0; i < s; i++) {
- int a, b;
- cin >> a >> b;
- a--; b--;
- safe_graph[a].push_back(b);
- safe_graph[b].push_back(a);
- }
- for(int i = 0; i < n; i++) {
- int res = sz[find_root(i)] - 1;
- // cout << res << endl;
- res -= (int) danger_graph[i].size();
- for(int j = 0; j < (int) safe_graph[i].size(); j++) {
- int neighbour = safe_graph[i][j];
- if(check(i, neighbour)) {
- res--;
- }
- }
- cout << res << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment