Advertisement
YEZAELP

TUMSO-16: Fast Aid

Nov 23rd, 2021
718
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 K = 1e4 + 10;
  6. const int INF = 1e9;
  7. vector <int> g[N];
  8. int disc[N], low[N];
  9. bool vs[N];
  10. int mx = -INF, ans_u, ans_v;
  11.  
  12. int dis_cnt = 0;
  13. int tarjan(int u, int pre){
  14.  
  15.     vs[u] = true;
  16.     dis_cnt ++;
  17.     disc[u] = low[u] = dis_cnt;
  18.  
  19.     int node_cnt = 1;
  20.     for(auto v: g[u]){
  21.         if(v == pre) 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(low[v] > disc[u]){
  27.                 int cur_u = u, cur_v = v;
  28.                 if(cur_u > cur_v) swap(cur_u, cur_v);
  29.                 if(node_v_cnt > mx){
  30.                     mx = node_v_cnt;
  31.                     ans_u = cur_u;
  32.                     ans_v = cur_v;
  33.                 }
  34.                 else if(node_v_cnt == mx){
  35.                     if(cur_u + cur_v < ans_u + ans_v){
  36.                         ans_u = cur_u;
  37.                         ans_v = cur_v;
  38.                     }
  39.                     else if(cur_u + cur_v == ans_u + ans_v and cur_u < ans_u){
  40.                         ans_u = cur_u;
  41.                         ans_v = cur_v;
  42.                     }
  43.                 }
  44.             }
  45.         }
  46.         else{
  47.             low[u] = min(low[u], disc[v]);
  48.         }
  49.     }
  50.  
  51.     return node_cnt;
  52. }
  53.  
  54. int main(){
  55.  
  56.     int n, k;
  57.     scanf("%d %d", &n, &k);;
  58.  
  59.     for(int i=1;i<=k;i++){
  60.         int u, v;
  61.         scanf("%d %d", &u, &v);
  62.         g[u].push_back(v);
  63.         g[v].push_back(u);
  64.     }
  65.  
  66.     tarjan(1, 0);
  67.  
  68.     if(mx == -INF)
  69.         printf("OK!");
  70.     else
  71.         printf("%d %d", ans_u, ans_v);
  72.  
  73.     return 0;
  74. }
  75.  
Advertisement
RAW Paste Data Copied
Advertisement