SHARE
TWEET

C SCC

naeem043 Jun 8th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. void DFS_Visit(int u);
  4. void DFS_Visit2(int u);
  5. int g[6][6],gt[6][6],color[6],prev[6],d[6], f[6],t,flage = 0,cu[6],cv[6],ts[6],m=0,n=0,dfs2[6];
  6. char name[9][100] = {"Undershort","Pants","Belt","Shirt","Tie","Jacket","Socks","Shoes","Watch"};
  7.  
  8. void DFS(int g[6][6])
  9. {
  10.     int i,j,s=0,u,v;
  11.  
  12.     for(i=0; i<6; i++)
  13.     {
  14.         color[i] = 0;
  15.         prev[i] = 0;
  16.         d[i] = 999999;
  17.         f[i] = 999999;
  18.         dfs2[i] = 999999;
  19.     }
  20.     t = 0;
  21.     color[s] = 0;
  22.     prev[s] = 0;
  23.     d[s] = 0;
  24.  
  25.     for(j=0; j<6; j++)
  26.     {
  27.         if(color[j]==0)
  28.         {
  29.             DFS_Visit(j);
  30.         }
  31.     }
  32.  
  33.     printf("\n\n Sorted Nodes:\t\t");
  34.     for(j=0; j<6; j++)
  35.     {
  36.         if(color[j]==2)
  37.         {
  38.             DFS_Visit2(ts[j]);
  39.             printf("SCC:\n");
  40.             for(i=0; i<6; i++)
  41.             {
  42.                 printf("%d",dfs2[i]);
  43.             }
  44.  
  45.             for(i=0; i<6; i++)
  46.             {
  47.                 dfs2[i] = 9999;
  48.             }
  49.         }
  50.         printf("%d\t",ts[j]);
  51.  
  52.     }
  53.  
  54.     printf("\n\n Discovery Time:\t");
  55.     for(i=0; i<6; i++)
  56.         printf("%d\t",d[i]);
  57.  
  58.     printf("\n\n Finishing Time:\t");
  59.     for(i=0; i<6; i++)
  60.         printf("%d\t",f[i]);
  61.  
  62.     printf("\n\n Color:\t\t\t");
  63.     for(i=0; i<6; i++)
  64.         printf("%d\t",color[i]);
  65.  
  66.     printf("\n\n Topological List:\t");
  67.     for(i=5; i>=0; i--)
  68.         printf("%d\t",ts[i]);
  69.  
  70.  
  71. //    if(flage==1)
  72. //    {
  73. //        printf("\n\n This Graph is cyclic\n The Cyclic Edges are:\n");
  74. //        for(i=0;i<6;i++)
  75. //        {
  76. //             printf(" %d - %d\t",cu[i],cv[i]);
  77. //        }
  78. //
  79. //    }
  80. //
  81. //    else printf("\n This Graph is not cycle");
  82.  
  83. }
  84.  
  85. void DFS_Visit(int u)
  86. {
  87.     int i,k = 0, l= 0;
  88.     color[u] = 1;
  89.     t = t+1;
  90.     d[u] = t;
  91.  
  92.     for(i=0; i<=5; i++)
  93.     {
  94.         if(color[i]==0 && g[u][i] !=0)
  95.         {
  96.             prev[i] = u;
  97.             DFS_Visit(i);
  98.         }
  99.         else if(color[i]==1 && g[u][i] !=0)
  100.         {
  101.             flage = 1;
  102.             cu[k] = u;
  103.             cv[l++] = i;
  104.             //printf("cycle edge %d\n", i);
  105.  
  106.             k++;
  107.             l++;
  108.         }
  109.     }
  110.     color[u] = 2;
  111.     t = t+1;
  112.     f[u] = t;
  113.     ts[m] = u;
  114.     m++;
  115. }
  116.  
  117. void DFS_Visit2(int u)
  118. {
  119.     int i,k = 0, l= 0;
  120.     color[u] = 1;
  121.     t = t+1;
  122.     d[u] = t;
  123.  
  124.     for(i=0; i<=5; i++)
  125.     {
  126.         if(color[i]==0 && g[u][i] !=0)
  127.         {
  128.             prev[i] = u;
  129.             DFS_Visit2(i);
  130.         }
  131.         else if(color[i]==1 && g[u][i] !=0)
  132.         {
  133.             flage = 1;
  134.             cu[k] = u;
  135.             cv[l++] = i;
  136.             //printf("cycle edge %d\n", i);
  137.  
  138.             k++;
  139.             l++;
  140.         }
  141.     }
  142.     color[u] = 2;
  143.     t = t+1;
  144.     f[u] = t;
  145.     ts[m] = u;
  146.     dfs2[n] = u;
  147.     m++;
  148.     n++;
  149.  
  150.  
  151. }
  152.  
  153.  
  154. int main()
  155. {
  156.     int i,j;
  157.  
  158.     for(i=0; i<6; i++)
  159.     {
  160.         for(j=0; j<6; j++)
  161.         {
  162.             g[i][j] = 0;
  163.         }
  164.  
  165.     }
  166. // Graph initialize
  167.     g[0][2] = 1;
  168.  
  169.     g[1][0] = 1;
  170.     g[1][3] = 1;
  171.  
  172.     g[2][1] = 1;
  173.     g[2][3] = 1;
  174.     g[2][5] = 1;
  175.  
  176.     g[3][4] = 1;
  177.  
  178.     g[4][3] = 1;
  179.  
  180.     g[5][5] = 1;
  181.  
  182.     for(i=0; i<6; i++)
  183.     {
  184.         for(j=0; j<6; j++)
  185.         {
  186.             printf(" %d ",g[i][j]);
  187.             gt[i][j] = g[j][i];
  188.         }
  189.         printf("\n");
  190.     }
  191.  
  192.     //Transpose graph
  193.     printf("\nTranspose graph:\n\n");
  194.     for(i=0; i<6; i++)
  195.     {
  196.         for(j=0; j<6; j++)
  197.         {
  198.             printf(" %d ",gt[i][j]);
  199.         }
  200.         printf("\n");
  201.     }
  202.     DFS(g);
  203.  
  204.     return 0;
  205. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top