Articulation Points and Bridges

Resource:

বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট [ থিওরি ]

গ্রাফ থিওরিতে হাতেখড়ি ১৩: আর্টিকুলেশন পয়েন্ট এবং ব্রিজ

Visualization

CF blog 

Finding bridges in a graph in O(N+M)

Finding articulation points in a graph in O(N+M)

Articulation Points:01

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

#include<bits/stdc++.h> using namespace std; #define Max 100000 vector<int> graph[Max]; int parent[Max]; int low[Max]; int d[Max]; int visited[Max]; bool isArticulationPoint[Max]; int Time = 0; void dfs(int u, int root) { Time = Time + 1; visited[u] = Time; d[u] = low[u] = Time; int noOfChildren = 0; for(int i = 0; i <graph[u].size(); i++){ int v = graph[u][i]; if(v == parent[u])continue; parent[v] = u; if(visited[v]) low[u] = min(low[u], d[v]); else{ noOfChildren = noOfChildren + 1; dfs(v, root); low[u] = min(low[u], low[v]); if(low[v] >= d[u] and u != root)isArticulationPoint[u] = true; } } if(u == root and noOfChildren > 1)isArticulationPoint[u] = true; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt", "r", stdin); int n,e; cin >> n >> e; for(int i = 0; i < e; i++){ int u,v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } dfs(1,1); for(int i = 1; i <= n; i++){ if(isArticulationPoint[i])cout << i<<endl; } return 0; }

Bridge 01:

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

#include<bits/stdc++.h> using namespace std; #define Max 100000 vector<int> graph[Max]; vector<pair<int, int> > Bridge; int parent[Max]; int low[Max]; int d[Max]; int visited[Max]; bool isArticulationPoint[Max]; int Time = 0; void dfs(int u, int root) { int v; Time = Time + 1; visited[u] = Time; d[u] = low[u] = Time; int noOfChildren = 0; for(int i = 0; i <graph[u].size(); i++){ v = graph[u][i]; if(v == parent[u])continue; parent[v] = u; if(visited[v]) low[u] = min(low[u], d[v]); else{ noOfChildren = noOfChildren + 1; dfs(v, root); low[u] = min(low[u], low[v]); if(low[v] > d[u]) { isArticulationPoint[u] = true; // cout << u << "-------"<<v<<endl; Bridge.push_back({u,v}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("in.txt", "r", stdin); int n,e; cin >> n >> e; for(int i = 0; i < e; i++){ int u,v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } dfs(1,1); for(int i = 0; i < Bridge.size(); i++){ cout << Bridge[i].first << " "<<Bridge[i].second<<endl; } return 0; }

Share: