fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define ii pair<int, int>
  4. using namespace std;
  5. const int N = 2e5+5;
  6.  
  7. string s;
  8. int n, m, ans[N];
  9. vector<int> g[N];
  10.  
  11. int parA[N], szA[N];
  12. int parS[N];
  13. bool onV[N];
  14. int cntPair = 0;
  15.  
  16. int find_parA(int x) { return parA[x] == x ? x : parA[x] = find_parA(parA[x]); }
  17.  
  18. void MergeA(int a, int b){
  19.     a = find_parA(a); b = find_parA(b);
  20.     if(a == b) return;
  21.     parA[b] = a;
  22.     cntPair += szA[a] * szA[b];
  23.     szA[a] += szA[b];
  24. }
  25.  
  26. int find_parS(int x) { return parS[x] == x ? x : parS[x] = find_parS(parS[x]); }
  27.  
  28. void MergeS(int a, int b){
  29.     a = find_parS(a); b = find_parS(b);
  30.     if(a != b) parS[b] = a;
  31. }
  32.  
  33. int compId[N];
  34. int repComp[N];
  35.  
  36. signed main() {
  37.     cin.tie(0)->sync_with_stdio(0);
  38.  
  39.     cin >> n >> m >> s; 
  40.     s = ' ' + s;
  41.  
  42.     for(int i=1; i<=n; ++i){
  43.         parA[i] = i; szA[i] = 1; onV[i] = 0;
  44.         parS[i] = i; repComp[i] = 0; compId[i] = 0;
  45.     }
  46.  
  47.     vector<ii> adj;
  48.     for(int i=0; i<m; ++i){
  49.         int u, v; cin >> u >> v;
  50.         g[u].push_back(v);
  51.         g[v].push_back(u);
  52.         adj.push_back({u, v});
  53.     }
  54.  
  55.     for(auto [u,v] : adj)
  56.         if(s[u] == '1' && s[v] == '1') 
  57.             MergeS(u, v);
  58.  
  59.     for(int i=1; i<=n; ++i)
  60.         if(s[i] == '1') 
  61.             compId[i] = find_parS(i);
  62.  
  63.     for(int t=n; t>0; --t){
  64.         onV[t] = 1;
  65.         szA[t] = 1;
  66.         parA[t] = t;
  67.  
  68.         for(int v : g[t]){
  69.             if(onV[v])
  70.                 MergeA(t, v);
  71.             else if(s[v] == '1') {
  72.                 int k = compId[v];
  73.                     int r = repComp[k];
  74.                     if(r) MergeA(t, r);
  75.                     repComp[k] = find_parA(t);
  76.             }
  77.         }
  78.  
  79.         ans[t] = cntPair;
  80.     }
  81.  
  82.     for(int i=1; i<=n; ++i)
  83.         cout << ans[i] << '\n';
  84.  
  85.     return 0;
  86. }
Success #stdin #stdout 0.01s 9584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/akzWKA
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!