A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks.
For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.
There are two ways to solve articulation point problems.
A) For every vertex v, do following
…..a) Remove v from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add v back to the graph
For this algorithm time complexity is O(V*(V+E))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <cstdio> #include <vector> #include <sstream> #include <string> #include <queue> #include <cstring> using namespace std; vector<int> gr[105]; bool visit[105]; int N; int bfs(int s) { visit[s]=1; queue<int> q; q.push(s); while(!q.empty()) { int a = q.front(); q.pop(); for(int i=0;i<gr[a].size();i++) { if(!visit[gr[a][i]]) { visit[gr[a][i]]=1; q.push(gr[a][i]); } } } for(int i=1;i<=N;i++) { if(visit[i]==0) return 1; } return 0; } int main() { int n,a; string s; while(scanf("%d",&N),N) { getchar(); if(N==1) { cin>>a; cout<<0<<"\n"; continue; } for(int i=0;i<105;i++) { gr[i].clear(); visit[i]=false; } while(getline(cin,s)) { stringstream ss; ss<<s; ss>>n; if(n==0) break; while(ss>>a) { gr[n].push_back(a); gr[a].push_back(n); } } int cnt=0; for(int i=2;i<=N;i++) { memset(visit,0,sizeof(visit)); visit[i]=1; if(bfs(1)) cnt+=1; } memset(visit,0,sizeof(visit)); visit[1]=1; if(bfs(2)) cnt+=1; cout<<cnt<<"\n"; } return 0; } |
B)Linear time algorithm :: Tarjan’s algorithm
Time complexity O(V+E).It is a DFS based solution. Articulation point connects two (or more) sub graphs. In a DFS tree a vertex u is articulation point iff it follows one of the following two rules.
a)u is root of DFS tree and it has at least two children.
b)If u is not root of DFS tree and it has a child v such that no vertex in sub tree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <cstdio> #include <vector> #include <sstream> #include <string> #include <queue> #include <cstring> using namespace std; vector<int> gr[105]; bool visit[105]; int N; int low[105]; int disc[105]; int par[105]; bool ap[105]; void cutvertex(int u) { static int disc_time = 0; low[u]=disc[u]=disc_time++; int child = 0; visit[u]=1; for(int i=0;i<gr[u].size();i++) { int v = gr[u][i]; if(visit[v]==0) { child++; par[v]=u; cutvertex(v); low[u]=min(low[u],low[v]); // u is an articulation point in following cases // (1) u is root of DFS tree and has two or more chilren. if(par[u]==-1 && child>1) { ap[u]=true; } // (2) If u is not root and low value of one of its child is more // than discovery value of u. else if(par[u]!=-1 && low[v]>=disc[u]) { ap[u]=true; } } else if(v!=par[u]) low[u]=min(low[u],disc[v]); } } int main() { int n,a; string s; while(scanf("%d",&N),N) { getchar(); if(N==1) { cin>>a; cout<<0<<"\n"; continue; } for(int i=0;i<105;i++) { gr[i].clear(); visit[i]=false; } while(getline(cin,s)) { stringstream ss; ss<<s; ss>>n; if(n==0) break; while(ss>>a) { gr[n].push_back(a); gr[a].push_back(n); } } for(int i=0;i<105;i++) { par[i]=-1;low[i]=0;disc[i]=0;ap[i]=0; } for(int i=1;i<=N;i++) { if(visit[i]==0) cutvertex(i); } int articulate_pnt = 0; for(int i=1;i<=N;i++) { if(ap[i]) articulate_pnt++; } cout<<articulate_pnt<<"\n"; } return 0; } |