Advertisement
Josif_tepe

Untitled

Dec 26th, 2022
797
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. using namespace std;
  9. const int maxn = 1e5 + 10;
  10. int n, m;
  11. vector<int> dangerous_graph[maxn];
  12. vector<int> safe_graph[maxn];
  13.  
  14. int idx[maxn], sz[maxn];
  15. int find_root(int x) {
  16.     while(x != idx[x]) {
  17.         idx[x] = idx[idx[x]];
  18.         x = idx[x];
  19.     }
  20.     return x;
  21. }
  22. bool check(int a, int b) {
  23.     if(find_root(a) == find_root(b)) {
  24.         return true;
  25.     }
  26.     return false;
  27. }
  28. void unite(int a, int b) {
  29.     int a_root = find_root(a);
  30.     int b_root = find_root(b);
  31.    
  32.     if(a_root != b_root) {
  33.        
  34.         if(sz[a_root] < sz[b_root]) {
  35.             idx[a_root] = idx[b_root];
  36.             sz[b_root] += sz[a_root];
  37.         }
  38.         else {
  39.             idx[b_root] = idx[a_root];
  40.             sz[a_root] += sz[b_root];
  41.         }
  42.        
  43.     }
  44.    
  45. }
  46. int main() {
  47.     for(int i = 0; i < maxn; i++) {
  48.         idx[i] = i;
  49.         sz[i] = 1;
  50.     }
  51.    
  52.     cin >> n >> m;
  53.     for(int i = 0; i < m; i++) {
  54.         int a, b;
  55.         cin >> a >> b;
  56.         a--;
  57.         b--;
  58.         dangerous_graph[a].push_back(b);
  59.         dangerous_graph[b].push_back(a);
  60.         unite(a, b);
  61.     }
  62.     int k;
  63.     cin >> k;
  64.     for(int i = 0; i < k; i++) {
  65.         int a, b;
  66.         cin >> a >> b;
  67.         a--;
  68.         b--;
  69.         safe_graph[a].push_back(b);
  70.         safe_graph[b].push_back(a);
  71.     }
  72.     for(int i = 0; i < n; i++) {
  73.         int result = sz[find_root(i)] - 1;
  74.         result -= (int) dangerous_graph[i].size();
  75. //        cout << i << " " << sz[find_root(i)] << " " << dangerous_graph[i].size() << endl;
  76.         for(int j = 0; j < safe_graph[i].size(); j++) {
  77.             int neighbour = safe_graph[i][j];
  78.             if(check(neighbour, i)) {
  79.                 result--;
  80.             }
  81.         }
  82.         cout << result << endl;
  83.     }
  84.     return 0;
  85. }
  86. /*
  87.  10 9
  88.  1 6
  89.  1 9
  90.  1 10
  91.  2 6
  92.  2 7
  93.  3 7
  94.  4 8
  95.  4 9
  96.  5 10
  97.  */
  98.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement