Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- int v,t;
- int matrix[100][100];
- int clr[100],dis[100],fin[100],prev[100];
- int t_edge,b_edge,f_edge,c_edge;
- void DFS();
- void DFS_visit(int s);
- int main()
- {
- int r,c,n,s;
- int edge=1;
- cout<<"Input No Of Vertices: ";
- cin>>v;
- do
- {
- cout<<"Edge "<<edge<<": "<<endl;
- cin>>r>>c;
- if(r>v || c>v)
- cout<<"Invalid Input"<<endl;
- else
- {
- matrix[r][c]=1;
- edge++;
- }
- }while(r!=0 && c!=0);
- DFS();
- return 0;
- }
- void DFS()
- {
- int i;
- t=0;
- t_edge=0;
- b_edge=0;
- f_edge=0;
- c_edge=0;
- for(i=0;i<=v;i++)
- {
- dis[i]=2000000;
- fin[i]=2000000;
- clr[i]=0;
- prev[i]=-1;
- }
- for(i=1;i<=v;i++){
- if(clr[i]==0)
- {
- DFS_visit(i);
- }
- }
- cout<<endl<<"Vertex: ";
- for(i=1;i<=v;i++)
- cout<<i<<" ";
- cout<<endl<<"dis[u]: ";
- for(i=1;i<=v;i++)
- cout<<dis[i]<<" ";
- cout<<endl<<"fin[u]: ";
- for(i=1;i<=v;i++)
- cout<<fin[i]<<" ";
- cout<<endl;
- cout<<endl;
- cout<<endl;
- cout<<"No Of Tree Edges: "<<t_edge<<endl;
- cout<<"No Of forward Edges: "<<f_edge<<endl;
- cout<<"No Of Back Edges: "<<b_edge<<endl;
- cout<<"No Of cross Edges: "<<c_edge<<endl;
- }
- void DFS_visit(int s)
- {
- int i;
- clr[s]=1;
- t=t+1;
- dis[s]=t;
- for(i=1;i<=v;i++)
- {
- if(matrix[s][i]==1 && clr[i]==0)
- {
- prev[i]=s;
- t_edge++;
- DFS_visit(i);
- }
- else if(matrix[s][i]==1 && clr[i]==1)
- b_edge++;
- else
- {
- if(matrix[s][i]==1 && clr[i]==2)
- {
- if(dis[s]<dis[i])
- f_edge++;
- else
- c_edge++;
- }
- }
- }
- clr[s]=2;
- t=t+1;
- fin[s]=t;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement