Advertisement
YEZAELP

TOI12: weakpoint (Tarjan)

Nov 23rd, 2021
708
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 = 5e5 + 10;
  5. vector <int> g[N];
  6. int ans_max = 0, ans_node = N;
  7. int disc[N], low[N];
  8. bool vs[N];
  9.  
  10. int dis_cnt = 0;
  11. int tarjan(int u, int pre){
  12.  
  13.     dis_cnt ++;
  14.     disc[u] = low[u] = dis_cnt;
  15.     vs[u] = true;
  16.     int node_cnt = 1;
  17.     bool is_art = false;
  18.     int art_cnt = 0;
  19.  
  20.     for(auto v: g[u]){
  21.         if(pre == v) continue;
  22.         if(!vs[v]){
  23.             int node_v_cnt = tarjan(v, u);
  24.             node_cnt += node_v_cnt;
  25.             low[u] = min(low[u], low[v]);
  26.             if(pre != 0 and low[v] >= disc[u]){
  27.                 is_art = true;
  28.                 art_cnt += node_v_cnt;
  29.             }
  30.         }
  31.         else{
  32.             low[u] = min(low[u], disc[v]);
  33.         }
  34.     }
  35.  
  36.     if(is_art){
  37.         if(art_cnt > ans_max){
  38.             ans_max = art_cnt;
  39.             ans_node = u;
  40.         }
  41.         else if(art_cnt == ans_max)
  42.             ans_node = min(ans_node, u);
  43.     }
  44.  
  45.     return node_cnt;
  46. }
  47.  
  48. int main(){
  49.  
  50.     int n, m;
  51.     scanf("%d%d", &n, &m);
  52.  
  53.     for(int i=1;i<=n;i++){
  54.         int u, v; scanf("%d %d", &u, &v);
  55.         ans_node = min(ans_node, u);
  56.         ans_node = min(ans_node, v);
  57.         g[u].push_back(v);
  58.         g[v].push_back(u);
  59.     }
  60.  
  61.     tarjan(m, 0);
  62.  
  63.     if(ans_max == 0) printf("%d\n0", m == 1 ? 2: 1);
  64.     else printf("%d\n%d", ans_node, ans_max);
  65.  
  66.     return 0;
  67. }
Advertisement
RAW Paste Data Copied
Advertisement