Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //int matrix[100][100];
- list<int> adj[100];
- char clr[100];
- int d[100];
- int f[100];
- int prev[100];
- int t,v;
- int low[100];
- vector<int> point;
- void visit_dfs(int u)
- {
- clr[u]='g';
- t=t+1;
- d[u]=t;
- low[u]=d[u];
- int n=0;
- for(list<int>::iterator it=adj[u].begin();it!=adj[u].end();it++)
- {
- if(clr[*it]=='w')
- {
- n++;
- prev[*it]=u;
- visit_dfs(*it);
- low[u]=min(low[u],low[*it]);
- if(prev[u]==-1 && n>1)
- {
- point.push_back(u);
- }
- if (low[*it] >= d[u] && prev[u]!=-1)
- {
- point.push_back(u);
- }
- }
- else if(*it != prev[u])
- {
- low[u]=min(low[u],d[*it]);
- }
- }
- /*for(int i=1;i<=v;i++)
- {
- if(matrix[u][i]==1 && clr[i]=='w')
- {
- prev[i]=u;
- visit_dfs(i);
- }
- }*/
- clr[u]='b';
- t=t+1;
- f[u]=t;
- }
- void dfs()
- {
- for(int i=1;i<=v;i++)
- {
- clr[i]='w';
- prev[i]=-1;
- f[i]=10000000;
- d[i]=10000000;
- low[i]=1000000;
- }
- t=0;
- for(int i=1;i<=v;i++)
- {
- if(clr[i]=='w')
- {
- visit_dfs(i);
- }
- }
- }
- int main()
- {
- int a,b,k=1;
- cout<<"Enter number of Vartex : ";
- cin>>v;
- while(1)
- {
- cout<<"Edge "<<k<<" : ";
- cin>>a>>b;
- if(a>v || b>v)
- {
- cout<<"Wrong input"<<endl;
- }
- else if(a==0 && b==0)
- {
- break;
- }
- else
- {
- adj[a].push_back(b);
- adj[b].push_back(a);
- k++;
- }
- }
- dfs();
- for(int i=0;i<point.size();i++)
- {
- cout<<point[i]<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement