Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- string color[100000] = "white";
- int timee = 0;
- int d[100000],f[100000];
- class Node{
- public:
- int destination;
- int weight;
- Node *next;
- };
- class Integer{
- public:
- Node *head = NULL;
- };
- void addEdge(Integer arr[],int sorc,int dest)
- {
- Node *newNode = new Node();
- newNode->destination = dest;
- newNode->next = NULL;
- if( arr[sorc].head == NULL)
- arr[sorc].head = newNode;
- else
- {
- Node *temp = arr[sorc].head;
- while(temp->next != NULL)
- temp = temp->next;
- temp->next = newNode;
- }
- }
- void DFS_Visit(Integer arr[],int s,int prev[])
- {
- color[s] = "Gray";
- timee++;
- d[s] = timee;
- Node *temp = arr[s].head;
- cout<<s<< " "<<endl;
- while( temp!=NULL)
- {
- int child = temp->destination;
- if( color[child] == "white")
- {
- prev[child] = s;
- DFS_Visit(arr,child,prev);
- }
- temp = temp->next;
- }
- color[s] = "Black";
- timee = timee+1;
- f[s] = timee;
- }
- void DFS(Integer arr[],int prev[],int v){
- for(int i=1; i<=v; i++)
- {
- if(color[i] == "white")
- DFS_Visit(arr,i,prev);
- }
- }
- int main()
- {
- int prev[100000] = {0};
- freopen("input.txt","r",stdin);
- int v;
- cin>>v;
- Integer arr[v];
- /// eita na korle arr er vitore v+1 dite hobe
- for (int i = 0; i <= v; i++)
- arr[i].head = NULL;
- /// getting input
- int m,n;
- while(scanf("%d%d",&m,&n) == 2)
- {
- addEdge(arr,m,n);
- //addEdge(arr,n,m);
- }
- DFS(arr,prev,v);
- cout<<d[7]<<" "<<f[7]<<" "<<prev[7]<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement