fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5. using ii = pair < int , int >;
  6.  
  7. const int N = 1e5 + 5;
  8.  
  9.  
  10. int n;
  11. int s , d;
  12.  
  13. int code  (int x){ return x + n + 1; }
  14. int decode(int x){ return x - n - 1; }
  15.  
  16.  
  17. int low[N] , dfn[N];
  18. int timer = 0 , bcc_count = 0;
  19. int parent[N];
  20. bool cut[N];
  21.  
  22.  
  23. vector < int > adj[N] , Tree[N];
  24.  
  25. set < int > BCC[N];
  26. set < int > belong[N];
  27. set < int > ans;
  28.  
  29. vector < ii > edges_stack;
  30.  
  31. /// find bi-connected components /////////////////////////////////
  32.  
  33.  
  34. void make_BCC(int u , int v){
  35.     if(edges_stack.size() == 0)return;
  36.     bcc_count ++;
  37.  
  38.     ii E = {u , v};
  39.  
  40.     while( !edges_stack.empty() ){
  41.         ii E2 = edges_stack.back(); edges_stack.pop_back();
  42.  
  43.         int x = E2.first;
  44.         int y = E2.second;
  45.  
  46.         BCC[bcc_count].insert(x);
  47.         BCC[bcc_count].insert(y);
  48.  
  49.         belong[x].insert(bcc_count);
  50.         belong[y].insert(bcc_count);
  51.  
  52.         if(E2 == E)break;
  53.     }
  54. }
  55.  
  56. void dfs(int u , int p){
  57.     dfn[u] = low[u] = ++ timer;
  58.     int children = 0;
  59.  
  60.     for(int v : adj[u]){
  61.  
  62.         if(dfn[v] == 0){
  63.             children ++;
  64.             edges_stack.push_back({u , v});
  65.  
  66.             dfs(v , u);
  67.  
  68.             low[u] = min(low[u] , low[v]);
  69.  
  70.             if( (p == -1 && children > 1) || (p != -1 && dfn[u] <= low[v]) ){
  71.                 cut[u] = 1;
  72.                 make_BCC(u , v);
  73.             }
  74.  
  75.         }
  76.         else if(v != p){
  77.             if(dfn[v] < low[u]){
  78.                 low[u] = dfn[v];
  79.                 edges_stack.push_back({u , v});
  80.             }
  81.         }
  82.     }
  83. }
  84.  
  85. /// ///////////////////////////////////////////////////////////
  86.  
  87. /// build bi-connected components Tree ////////////////////////
  88.  
  89. /// connect each cut point to all component it belongs to
  90. void build_BCC_Tree(){
  91.  
  92.     for(int i = 0 ; i < n ; i ++){
  93.         if(cut[i]){
  94.             for(int b : belong[i]){
  95.                 int v = code(b);
  96.  
  97.                 Tree[i].push_back(v);
  98.                 Tree[v].push_back(i);
  99.             }
  100.         }
  101.     }
  102.  
  103. }
  104.  
  105. /// ///////////////////////////////////////////////////////////
  106.  
  107.  
  108. /// dfs the bi-connected components Tree
  109.  
  110. void dfs_Tree(int u , int p){
  111.     parent[u] = p;
  112.  
  113.     for(int v : Tree[u])if(v != p)dfs_Tree(v , u);
  114. }
  115.  
  116.  
  117. main(){
  118.     scanf("%d" , &n);
  119.  
  120.     for( ; ; ){
  121.         int u , v;
  122.  
  123.         scanf("%d %d" , &u , &v);
  124.         if(u == -1 && v == -1)break;
  125.  
  126.         adj[u].push_back(v);
  127.         adj[v].push_back(u);
  128.  
  129.     }
  130.     scanf("%d %d" , &s , &d);
  131.  
  132.     /// same city
  133.     if(s == d){
  134.         printf("%d\n" , s);
  135.         return 0;
  136.     }
  137.  
  138.     for(int i = 0 ; i < n ; i ++){
  139.         if(dfn[i] == 0){
  140.             dfs(i , -1);
  141.             make_BCC(-1 , -1);
  142.         }
  143.     }
  144.  
  145.     build_BCC_Tree();
  146.  
  147.     /// s is not a cut point so work with its bi-connected component
  148.     if(!cut[s])s = code(*(belong[s].begin()));
  149.  
  150.     /// same for d
  151.     if(!cut[d])d = code(*(belong[d].begin()));
  152.  
  153.     dfs_Tree(s , -1);
  154.  
  155.     /// now get the path from d to s
  156.     while( true ){
  157.         /// a cut point
  158.         if(d < n)ans.insert(d);
  159.  
  160.         /// a bi-connected component
  161.         else {
  162.             int comp = decode(d);
  163.             for(int B : BCC[comp])ans.insert(B);
  164.         }
  165.         if(d == s)break;
  166.         d = parent[d];
  167.         if(d == -1)break;
  168.     }
  169.  
  170.     int i = 0;
  171.     int sz = ans.size();
  172.     for(auto it = ans.begin() ; it != ans.end() ; it ++ , i ++){
  173.         printf("%d%s" , *it , i == sz-1 ? "" : " ");
  174.     }
  175.  
  176.     return 0;
  177. }
Success #stdin #stdout 0.01s 17924KB
comments (?)
stdin
copy 
20
0 1
1 2
2 3
3 4
4 5
5 6
6 7
1 8
8 11
8 9
9 10
11 12
9 12
12 13
12 15
12 14
14 19
14 18
14 17
17 18
18 19
13 15
15 16
-1 -1
10 16
stdout
copy 
8 9 10 11 12 13 15 16
https://ideone.com/5sFYmP
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!