Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cstring>
- #define DFS_WHITE 0
- using namespace std;
- typedef vector <int> vi;
- vector <vi> adjList;
- vi dfs_parent, dfs_low, dfs_num;
- vector <bool> articulationVertex;
- int dfsNumberCounter, dfsRoot, rootChildren;
- void isArticulationPoint(int u)
- {
- dfs_num[u] = dfs_low[u] = dfsNumberCounter++;
- for(int i = 0; i < (int)adjList[u].size(); ++i)
- {
- int v = adjList[u][i];
- if(dfs_num[v] == DFS_WHITE)
- {
- dfs_parent[v] = u;
- if(u == dfsRoot) rootChildren++;
- isArticulationPoint(v);
- if(dfs_low[v] >= dfs_num[u]) articulationVertex[u] = true;
- dfs_low[u] = min(dfs_low[v], dfs_low[u]);
- }
- else if(v != dfs_parent[u]) dfs_low[u] = min(dfs_low[u], dfs_num[v]);
- }
- }
- int main()
- {
- int n;
- while(scanf("%d", &n) && n != 0)
- {
- adjList.assign(n, vi());
- dfs_parent.assign(n, 0);
- dfs_low.assign(n, 0);
- dfs_num.assign(n, DFS_WHITE);
- articulationVertex.assign(n, false);
- dfsNumberCounter = 0;
- char linha[100001];
- while(gets(linha) && linha[0] != '0')
- {
- int tam = strlen(linha);
- int toConnect = linha[0] - '0';
- toConnect--;
- for(int i = 1; i < tam; ++i)
- {
- if(linha[i] != ' ')
- {
- int toConnectSecundary = linha[i] - '0';
- toConnectSecundary--;
- adjList[toConnect].push_back(toConnectSecundary);
- adjList[toConnectSecundary].push_back(toConnect);
- }
- }
- }
- for(int i = 0; i < n; ++i)
- {
- if(dfs_num[i] == DFS_WHITE)
- {
- dfsRoot = i; rootChildren = 0;
- isArticulationPoint(i);
- articulationVertex[dfsRoot] = (rootChildren > 1);
- }
- }
- int howMany = 0;
- for(int i = 0; i < n; ++i)
- {
- if(articulationVertex[i]) howMany++;
- }
- printf("%d\n", howMany);
- }
- }
Add Comment
Please, Sign In to add comment