Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- void DFS_Visit(int u);
- int g[9][9],color[7],prev[9],d[9], f[9],t,flage = 0,cu[9],cv[9],ts[9],m=0;
- char name[9][100] = {"Undershort","Pants","Belt","Shirt","Tie","Jacket","Socks","Shoes","Watch"};
- void DFS(int g[9][9])
- {
- int i,j,s=0,u,v;
- for(i=0;i<9;i++)
- {
- color[i] = 0;
- prev[i] = 0;
- d[i] = 999999;
- f[i] = 999999;
- }
- t = 0;
- color[s] = 0;
- prev[s] = 0;
- d[s] = 0;
- for(j=0;j<9;j++)
- {
- if(color[j]==0)
- {
- DFS_Visit(j);
- }
- }
- printf("\n Discovery Time:\t");
- for(i=0;i<9;i++)
- printf("%d\t",d[i]);
- printf("\n Finishing Time:\t");
- for(i=0;i<9;i++)
- printf("%d\t",f[i]);
- printf("\n Color:\t\t\t");
- for(i=0;i<9;i++)
- printf("%d\t",color[i]);
- printf("\n Topological List:\t");
- for(i=8;i>=0;i--)
- printf("%d ",ts[i]);
- printf("\n Shopping List:\t");
- for(i=8;i>=0;i--)
- printf("%s ",name[ts[i]]);
- if(flage==1)
- {
- printf("\n This Graph is cycle\nTheCycle Edges are:\n");
- for(i=0;i<9;i++)
- {
- printf("%d - %d\t",cu[i],cv[i]);
- }
- }
- else printf("\n This Graph is not cycle");
- }
- void DFS_Visit(int u)
- {
- int i,k = 0, l= 0;
- color[u] = 1;
- t = t+1;
- d[u] = t;
- for(i=0;i<8;i++)
- {
- if(color[i]==0 && g[u][i] !=0)
- {
- prev[i] = u;
- DFS_Visit(i);
- }
- else if(color[i]==1 && g[u][i] !=0)
- {
- flage = 1;
- cu[k] = u;
- cv[l++] = i;
- //printf("cycle edge %d\n", i);
- k++;
- l++;
- }
- }
- color[u] = 2;
- t = t+1;
- f[u] = t;
- ts[m] = u;
- m++;
- }
- int main()
- {
- int i,j;
- for(i=0;i<9;i++)
- {
- for(j=0;j<9;j++)
- {
- g[i][j] = 0;
- }
- }
- // Graph initialize
- g[0][1] = 1;
- g[0][7] = 1;
- g[1][2] = 1;
- g[1][7] = 1;
- g[2][5] = 1;
- g[3][4] = 1;
- g[4][5] = 1;
- g[6][7] = 1;
- for(i=0;i<9;i++)
- {
- for(j=0;j<9;j++)
- {
- printf("%d ",g[i][j]);
- }
- printf("\n");
- }
- DFS(g);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement