Josif_tepe

Untitled

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