fork(2) download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define INF 1e9
  6.  
  7. const int UNVISITED = -1;
  8. const int VISITED = 0;
  9.  
  10. vector<int> graph[105];
  11. bool isArticulationPoint[105];
  12. int dfs_status[105];
  13. int dfs_parent[105];
  14. int dfs_depth[105];
  15. int dfs_low[105];
  16.  
  17. void dfsArticulationPoints(int u)
  18. {
  19.     dfs_status[u] = VISITED;
  20.  
  21.     dfs_low[u] = dfs_depth[u];
  22.  
  23.     int childrensCount = 0;
  24.     bool articulationPoint = false;
  25.  
  26.     for (auto v: graph[u])
  27.     {
  28.         if (dfs_status[v] == UNVISITED)
  29.         {
  30.             dfs_depth[v] = dfs_depth[u] + 1;
  31.             childrensCount++;
  32.  
  33.             dfs_parent[v] = u;
  34.             dfsArticulationPoints(v);
  35.  
  36.             if (dfs_low[v] >= dfs_depth[u])
  37.             {
  38.                 articulationPoint = true;
  39.             }
  40.             else
  41.             {
  42.                 dfs_low[u] = min(dfs_low[u], dfs_low[v]);
  43.             }
  44.         }
  45.         else if (dfs_parent[u] != v)
  46.         {
  47.             dfs_low[u] = min(dfs_low[u], dfs_depth[v]);
  48.         }
  49.     }
  50.  
  51.     if ((dfs_parent[u] == -1 && childrensCount >= 2) || (dfs_parent[u] != -1 && articulationPoint))
  52.     {
  53.         isArticulationPoint[u] = true;
  54.     }
  55. }
  56.  
  57. int main()
  58. {
  59.     #ifdef VSP4
  60.     freopen("input.txt", "r", stdin);
  61.     freopen("output.txt", "w", stdout);
  62.     #endif // VSP4
  63.  
  64.     int t, i, j, n, m, u, v, ans, zeroColored, oneColored;
  65.     string str;
  66.     stringstream ss;
  67.  
  68.     while (cin >> n >> ws, n)
  69.     {
  70.         for (i = 1; i <= n; i++)
  71.         {
  72.             graph[i].clear();
  73.         }
  74.  
  75.         while (getline(cin, str), ss.clear(), ss.str(str), ss >> u, u)
  76.         {
  77.             while (ss >> v)
  78.             {
  79.                 graph[u].push_back(v);
  80.                 graph[v].push_back(u);
  81.                 //cout << u << "-" << v << "\n";
  82.             }
  83.         }
  84.  
  85.         memset(dfs_status, UNVISITED, sizeof(dfs_status));
  86.         memset(isArticulationPoint, false, sizeof(isArticulationPoint));
  87.  
  88.         dfs_depth[1] = 0;
  89.         dfs_parent[1] = -1;
  90.         dfsArticulationPoints(1);
  91.  
  92.         ans = 0; //records no of articulation points
  93.  
  94.         for (i = 1; i <= n; i++)
  95.         {
  96.             if (isArticulationPoint[i])
  97.             {
  98.                 ans++;
  99.             }
  100.         }
  101.  
  102.         cout << ans << "\n";
  103.     }
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0
stdout 
1
2
https://ideone.com/vcbqE0
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!