#include <bits/stdc++.h>
using namespace std;
struct Graph {
int n, m;
vector<vector<int> > adj_list;
vector<int> enter, lower, cutV;
vector< pair<int, int> > cutE;
vector<bool> visited;
int timer = 0;
Graph(int v, int e) {
n = v, m = e;
adj_list = vector<vector<int> > (n + 1);
enter = vector<int> (n + 1);
lower = vector<int> (n + 1);
visited = vector<bool> (n + 1);
timer = 0;
}
void add_edges(int u, int v) {
adj_list[u].push_back(v);
//adj_list[v].push_back(u);
}
// Function for cut edges
void dfs(int u, int par = 0)
{
visited[u] = true;
timer++;
enter[u] = lower[u] = timer;
vector<int> :: iterator it;
for(it=adj_list[u].begin(); it!=adj_list[u].end(); it++)
{
int v=*it;
if (v == par) continue;
if (visited[v]) lower[u] = min(lower[u], enter[v]);
else {
dfs(v, u);
lower[u] = min(lower[u], lower[v]);
if (lower[v] > enter[u]) cutE.push_back(make_pair(u, v));
}
}
}
//Function for cut vertices
void dfs2(int u, int par = 0)
{
visited[u] = true;
int child = 0;
timer++;
enter[u] = lower[u] = timer;
vector<int> :: iterator it;
for(it=adj_list[u].begin();it!=adj_list[u].end();it++)
{
int v=*it;
if (v == par) continue;
if (visited[v]) lower[u] = min(lower[u], enter[v]);
else {
dfs2(v, u);
lower[u] = min(lower[u], lower[v]);
if (lower[v] >= enter[u] && par) {
cutV.push_back(u);
}
child++;
}
}
if (par == 0 && child >= 2) cutV.push_back(u);
}
void find_cutEdges() {
for (int i = 1; i <= n; i++) {
if (!visited[i]) dfs(i);
}
cout << "Cut Edges : " << endl;
vector<pair<int,int> > :: iterator it;
for(it=cutE.begin();it!=cutE.end();it++){
cout << (*it).first << " " << (*it).second << endl;
}
fill(visited.begin(), visited.end(), 0);
}
void find_cutVertices() {
for (int i = 1; i <= n; i++) {
if (!visited[i]) dfs2(i);
}
cout << "Cut Vertices : " << endl;
sort(cutV.begin(), cutV.end());
cout << cutV.front() << endl;
for (int i = 1; i < cutV.size(); i++) {
if (cutV[i] != cutV[i - 1])
cout << cutV[i] << endl;
}
}
};
int main() {
cout<<"Enter number of vertices edges and graph : "<<endl;
int n, m; cin >> n >> m;
Graph g(n, m);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
g.add_edges(u, v);
g.add_edges(v, u);
}
g.find_cutEdges();
g.find_cutVertices();
cout << "----------------" << endl;
}
/*
4 4
1 2
2 3
3 4
2 4
*
Comments
Post a Comment