Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef struct
- {
- int id;
- char name;
- int start;
- int end;
- int color;
- } topo;
- topo ara[100];
- vector<int>v[100];
- int cnt=1;
- int cmp(topo a,topo b)
- {
- return a.end>b.end;
- }
- void dfs(int src)
- {
- if(ara[src].color==1)
- return;
- //printf("%c\n", src+'A');
- ara[src].color=1;
- ara[src].start=cnt++;
- for(int i=0; i<v[src].size(); i++)
- {
- // printf("%c ", v[src][i]);
- dfs(v[src][i]);
- }
- ara[src].end=cnt++;
- //printf("%c\n", src+'A');
- }
- int main()
- {
- int n,e,i,j;
- cin>>n>>e;
- for(i=0; i<e; i++)
- {
- char b,c;
- cin>>b>>c;
- int temp1=b-'A',temp2=c-'A';
- ara[temp1].id=temp1, ara[temp2].id=temp2;
- ara[temp1].name=b,ara[temp2].name=c;
- v[temp1].push_back(temp2);
- }
- for(i=0; i<n; i++)
- {
- printf("%c-->",ara[i].name);
- if(!v[i].empty())
- for(j=0; j<v[i].size(); j++)printf("%d ",v[i][j]);
- cout<<endl;
- }
- for(i=0; i<n; i++)
- {
- if(ara[i].color==0)
- dfs(ara[i].id);
- }
- for(i=0; i<n; i++)
- {
- printf("%d %c %d %d\n",ara[i].id,ara[i].name,ara[i].start,ara[i].end);
- }
- cout<<endl<<endl<<endl;
- sort(ara,ara+n,cmp);
- for(int i=0; i<n; i++)
- {
- cout << "Start of " << (char)(ara[i].id+'A') << " == " << ara[i].start << " And end of " << (char)(ara[i].id+'A') << " == " << ara[i].end << endl;
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement