Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 100000
- using namespace std;
- enum color {WHITE,GRAY,BLACK};
- vector<vector<int>> adjList;
- color vertex_color[MAX+1];
- int parent[MAX+1];
- int vertex_start[MAX+1];
- int vertex_end[MAX+1];
- int TIME = 0;
- int n,m;
- void addEdge(int u, int v)
- {
- adjList[u].push_back(v);
- }
- void DFS_VISIT(int u)
- {
- TIME = TIME+1;
- vertex_start[u] = TIME;
- vertex_color[u] = GRAY;
- cout << u << " ";
- for(int i = 0; i < adjList[u].size(); i++)
- {
- int v = adjList[u][i];
- if(vertex_color[v] == WHITE)
- {
- parent[v] = u;
- DFS_VISIT(v);
- }
- }
- vertex_color[u] = BLACK;
- TIME = TIME+1;
- vertex_end[u] = TIME;
- }
- void DFS()
- {
- for(int i = 1; i <= n; i++)
- {
- vertex_color[i] = WHITE;
- parent[i] = 0;
- }
- TIME = 0;
- for(int i = 1; i <= n; i++)
- {
- if(vertex_color[i] == WHITE)
- DFS_VISIT(i);
- cout << endl;
- }
- //DFS_VISIT(2);
- }
- int main()
- {
- freopen("a.txt","r",stdin);
- cin >> n >> m;
- adjList.resize(n+1);
- for(int i = 1; i <= m; i++)
- {
- int u,v;
- cin >> u >> v;
- addEdge(u,v);
- }
- DFS();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement