Advertisement
Guest User

Untitled

a guest
Oct 17th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl '\n'
  5. #define MAX 412
  6. #define NIL -1
  7.  
  8. int bg[MAX], low[MAX];
  9. vector<int> adj[MAX];
  10.  
  11. int T = 1;
  12. set <int> articulation;
  13.  
  14. void dfs (int v, int anc) {
  15.  
  16.     low[v] = bg[v] = T++;
  17.  
  18.     int children = 0;
  19.     for (int i = 0; i < adj[v].size(); i++) {
  20.         int u = adj[v][i];
  21.        
  22.         if( bg[u] == 0 ) {
  23.             children++;
  24.            
  25.             dfs(u, v);
  26.  
  27.             low[v] = min(low[v], low[u]);
  28.  
  29.             if (anc == NIL) {
  30.                 if (children > 1)
  31.                     articulation.insert(v);
  32.             }
  33.             else {
  34.                 if (bg[v] <= low[u])
  35.                     articulation.insert(v);
  36.             }
  37.         }
  38.         else if (u != anc)
  39.             low[v] = min(low[v], low[u]);
  40.     }
  41. }
  42.  
  43.  
  44. signed main() {
  45.     ios_base::sync_with_stdio(false);
  46.     cin.tie(0);
  47.     cout.tie(0);
  48.  
  49.     int N, M;
  50.     int test = 1;
  51.     for (cin >> N >> M; N; cin >> N >> M) {
  52.        
  53.         for (int n = 0; n < N; n++) {
  54.             low[n] = bg[n] = 0;
  55.             adj[n].clear();
  56.         }
  57.         articulation.clear();
  58.        
  59.         for (int m = 0; m < M; m++) {
  60.             int a, b;
  61.             cin >> a >> b;
  62.             a--, b--;
  63.             adj[a].push_back(b);
  64.             adj[b].push_back(a);
  65.         }
  66.  
  67.         for (int n = 0; n < N; n++)
  68.             if (!bg[n])
  69.                 dfs(n, NIL);
  70.  
  71.         cout << "Teste " << test++ << endl;
  72.  
  73.         if ( articulation.empty() )
  74.             cout << "nenhum";
  75.        
  76.         for(set<int>::iterator it = articulation.begin(); it != articulation.end(); ++it)
  77.             cout << *it + 1 << " ";
  78.        
  79.         cout << endl << endl;
  80.     }
  81.  
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement