Advertisement
jakaria_hossain

Topological Sort

Oct 23rd, 2018
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.55 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct
  4. {
  5. int id;
  6. char name;
  7. int start;
  8. int end;
  9. int color;
  10. } topo;
  11. topo ara[100];
  12. vector<int>v[100];
  13. int cnt=1;
  14. int cmp(topo a,topo b)
  15. {
  16. return a.end>b.end;
  17. }
  18. void dfs(int src)
  19. {
  20. if(ara[src].color==1)
  21. return;
  22. //printf("%c\n", src+'A');
  23. ara[src].color=1;
  24. ara[src].start=cnt++;
  25.  
  26. for(int i=0; i<v[src].size(); i++)
  27. {
  28. // printf("%c ", v[src][i]);
  29. dfs(v[src][i]);
  30. }
  31. ara[src].end=cnt++;
  32. //printf("%c\n", src+'A');
  33.  
  34. }
  35. int main()
  36. {
  37. int n,e,i,j;
  38. cin>>n>>e;
  39.  
  40. for(i=0; i<e; i++)
  41. {
  42. char b,c;
  43. cin>>b>>c;
  44. int temp1=b-'A',temp2=c-'A';
  45. ara[temp1].id=temp1, ara[temp2].id=temp2;
  46. ara[temp1].name=b,ara[temp2].name=c;
  47.  
  48. v[temp1].push_back(temp2);
  49. }
  50. for(i=0; i<n; i++)
  51. {
  52. printf("%c-->",ara[i].name);
  53.  
  54. if(!v[i].empty())
  55. for(j=0; j<v[i].size(); j++)printf("%d ",v[i][j]);
  56. cout<<endl;
  57. }
  58. for(i=0; i<n; i++)
  59. {
  60.  
  61. if(ara[i].color==0)
  62. dfs(ara[i].id);
  63. }
  64. for(i=0; i<n; i++)
  65. {
  66. printf("%d %c %d %d\n",ara[i].id,ara[i].name,ara[i].start,ara[i].end);
  67. }
  68. cout<<endl<<endl<<endl;
  69. sort(ara,ara+n,cmp);
  70. for(int i=0; i<n; i++)
  71. {
  72. cout << "Start of " << (char)(ara[i].id+'A') << " == " << ara[i].start << " And end of " << (char)(ara[i].id+'A') << " == " << ara[i].end << endl;
  73. }
  74. cout << endl;
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement