Guest User

Untitled

a guest
Jan 17th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cstring>
  6. #define DFS_WHITE 0
  7.  
  8. using namespace std;
  9.  
  10. typedef vector <int> vi;
  11.  
  12. vector <vi> adjList;
  13. vi dfs_parent, dfs_low, dfs_num;
  14. vector <bool> articulationVertex;
  15. int dfsNumberCounter, dfsRoot, rootChildren;
  16.  
  17. void isArticulationPoint(int u)
  18. {
  19.     dfs_num[u] = dfs_low[u] = dfsNumberCounter++;
  20.     for(int i = 0; i < (int)adjList[u].size(); ++i)
  21.     {
  22.         int v = adjList[u][i];
  23.         if(dfs_num[v] == DFS_WHITE)
  24.         {
  25.             dfs_parent[v] = u;
  26.             if(u == dfsRoot) rootChildren++;
  27.             isArticulationPoint(v);
  28.             if(dfs_low[v] >= dfs_num[u]) articulationVertex[u] = true;
  29.             dfs_low[u] = min(dfs_low[v], dfs_low[u]);
  30.         }
  31.         else if(v != dfs_parent[u]) dfs_low[u] = min(dfs_low[u], dfs_num[v]);
  32.     }
  33.  
  34. }
  35.  
  36. int main()
  37. {
  38.     int n;
  39.     while(scanf("%d", &n) && n != 0)
  40.     {
  41.         adjList.assign(n, vi());
  42.         dfs_parent.assign(n, 0);
  43.         dfs_low.assign(n, 0);
  44.         dfs_num.assign(n, DFS_WHITE);
  45.         articulationVertex.assign(n, false);
  46.         dfsNumberCounter = 0;
  47.         char linha[100001];
  48.         while(gets(linha) && linha[0] != '0')
  49.         {
  50.             int tam = strlen(linha);
  51.             int toConnect = linha[0] - '0';
  52.             toConnect--;
  53.             for(int i = 1; i < tam; ++i)
  54.             {
  55.                 if(linha[i] != ' ')
  56.                 {
  57.                     int toConnectSecundary = linha[i] - '0';
  58.                     toConnectSecundary--;
  59.                     adjList[toConnect].push_back(toConnectSecundary);
  60.                     adjList[toConnectSecundary].push_back(toConnect);
  61.                 }
  62.             }
  63.         }
  64.         for(int i = 0; i < n; ++i)
  65.         {
  66.             if(dfs_num[i] == DFS_WHITE)
  67.             {
  68.                 dfsRoot = i; rootChildren = 0;
  69.                 isArticulationPoint(i);
  70.                 articulationVertex[dfsRoot] = (rootChildren > 1);
  71.             }
  72.         }
  73.         int howMany = 0;
  74.         for(int i = 0; i < n; ++i)
  75.         {
  76.             if(articulationVertex[i]) howMany++;
  77.         }
  78.         printf("%d\n", howMany);
  79.  
  80.     }
  81. }
Add Comment
Please, Sign In to add comment