Advertisement
Josif_tepe

Untitled

Dec 18th, 2022
817
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. vector<int> dangerous_graph[maxn], safe_graph[maxn];
  6. int idx[maxn], size[maxn];
  7. int root(int x) {
  8.     while(x != idx[x]) {
  9.         idx[x] = idx[idx[x]];
  10.         x = idx[x];
  11.     }
  12.     return x;
  13. }
  14. void unify(int a, int b) {
  15.     int root_a = root(a);
  16.     int root_b = root(b);
  17.     if(root_a == root_b) {
  18.         return;
  19.     }
  20.     if(size[root_a] < size[root_b]) {
  21.         size[root_b] += size[root_a];
  22.         idx[root_a] = idx[root_b];
  23.     }
  24.     else {
  25.         size[root_a] += size[root_b];
  26.         idx[root_b] = idx[root_a];
  27.     }
  28. }
  29. int main() {
  30.     for(int i = 0; i < maxn; i++) {
  31.         idx[i] = i;
  32.         size[i] = 1;
  33.     }
  34.    
  35.     int n, m;
  36.     cin >> n >> m;
  37.    
  38.     for(int i = 0; i < m; i++) {
  39.         int a, b;
  40.         cin >> a >> b;
  41.         --a; --b;
  42.         dangerous_graph[a].push_back(b);
  43.         dangerous_graph[b].push_back(a);
  44.         unify(a, b);
  45.     }
  46.     int k;
  47.     cin >> k;
  48.     for(int i = 0; i < k; i++) {
  49.         int a, b;
  50.         cin >> a >> b;
  51.         --a; --b;
  52.         safe_graph[a].push_back(b);
  53.         safe_graph[b].push_back(a);
  54.     }
  55.    
  56.     vector<int> pairs(n);
  57.     for(int i = 0; i < n; i++) {
  58.         pairs[i] = size[root(i)];
  59.         pairs[i] -= (int) dangerous_graph[i].size();
  60.     }
  61.    
  62.     for(int i = 0; i < n; i++) {
  63.         for(int j = 0; j < (int) safe_graph[i].size(); j++) {
  64.             int neighbour = safe_graph[i][j];
  65.             if(root(neighbour) == root(i)) {
  66.                 pairs[i]--;
  67.             }
  68.         }
  69.     }
  70.     for(int i = 0; i < n; i++) {
  71.         cout << pairs[i] - 1 << '\n';
  72.     }
  73.     return 0;
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement