Advertisement
mickypinata

TUMSO16: Fast Aid

Nov 23rd, 2021
817
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e4 + 5;
  5.  
  6. vector<int> adj[N];
  7. int disc[N], low[N], dp[N], mx, ansU, ansV;
  8. bool visited[N];
  9.  
  10. int discCnt = 0;
  11. void DFS(int u, int p){
  12.     disc[u] = ++discCnt;
  13.     low[u] = disc[u];
  14.     visited[u] = true;
  15.     int cnt = 1;
  16.     for(int v : adj[u]){
  17.         if(v == p){
  18.             continue;
  19.         }
  20.         if(visited[v]){
  21.             low[u] = min(low[u], disc[v]);
  22.         } else {
  23.             DFS(v, u);
  24.             low[u] = min(low[u], low[v]);
  25.             cnt += dp[v];
  26.             if(low[v] > disc[u]){
  27.                 if(dp[v] > mx){
  28.                     mx = dp[v];
  29.                     ansU = u;
  30.                     ansV = v;
  31.                 } else if(dp[v] == mx){
  32.                     if(u + v < ansU + ansV){
  33.                         ansU = u;
  34.                         ansV = v;
  35.                     } else if(u + v == ansU + ansV){
  36.                         if(min(u, v) < min(ansU, ansV)){
  37.                             ansU = u;
  38.                             ansV = v;
  39.                         }
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     dp[u] = cnt;
  46. }
  47.  
  48. int main(){
  49.  
  50.     int nVertex, nEdge;
  51.     scanf("%d%d", &nVertex, &nEdge);
  52.     for(int i = 1; i <= nEdge; ++i){
  53.         int u, v;
  54.         scanf("%d%d", &u, &v);
  55.         adj[u].push_back(v);
  56.         adj[v].push_back(u);
  57.     }
  58.     DFS(1, 0);
  59.     if(mx == 0){
  60.         cout << "OK!";
  61.     } else {
  62.         cout << min(ansU, ansV) << ' ' << max(ansU, ansV);
  63.     }
  64.  
  65.     return 0;
  66. }
  67.  
Advertisement
RAW Paste Data Copied
Advertisement