Advertisement
YEZAELP

SPOJ: Submerging Islands

Nov 22nd, 2021
573
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e4 + 10;
  5. const int M = 1e5 + 10;
  6. vector <int> g[N];
  7. unordered_set <int> ap;
  8. bool vs[N];
  9. int disc[N], low[N];
  10.  
  11. void Setting();
  12.  
  13. int cnt = 0;
  14. void tarjan(int u, int pre){
  15.     vs[u] = true;
  16.     cnt ++;
  17.     disc[u] = cnt;
  18.     low[u] = cnt;
  19.     int child = 0;
  20.     for(auto v: g[u]){
  21.         if(!vs[v]){
  22.             child ++;
  23.             tarjan(v, u);
  24.             low[u] = min(low[u], low[v]);
  25.             if((pre != 0 and low[v] >= disc[u]) or (pre == 0 and child > 1))
  26.                 ap.insert(u);
  27.         }
  28.         else if(v != pre){
  29.             low[u] = min(low[u], disc[v]);
  30.         }
  31.     }
  32. }
  33.  
  34. void Solve(int n, int m){
  35.     for(int i=1;i<=m;i++){
  36.         int u, v;
  37.         scanf("%d %d", &u, &v);
  38.         g[u].push_back(v);
  39.         g[v].push_back(u);
  40.     }
  41.     tarjan(1, 0);
  42.     printf("%d", ap.size());
  43.     Setting();
  44. }
  45.  
  46. int main(){
  47.  
  48.     while(true){
  49.         int n, m;
  50.         scanf("%d %d", &n, &m);
  51.         if(n == 0 and m == 0) return 0;
  52.         Solve(n, m);
  53.         printf("\n");
  54.     }
  55.  
  56.     return 0;
  57. }
  58.  
  59. void Setting(){
  60.     for(int i=1;i<=N-10;i++){
  61.         if(!g[i].empty()) g[i].clear();
  62.     }
  63.     if(!ap.empty()) ap.clear();
  64.     for(int i=1;i<=N-10;i++){
  65.         vs[i] = false;
  66.         disc[i] = 0;
  67.         low[i] = 0;
  68.     }
  69. }
Advertisement
RAW Paste Data Copied
Advertisement