Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <stack>
- using namespace std;
- ifstream cin("topsort.in");
- ofstream cout("topsort.out");
- vector<vector<int>> g;
- vector<int> Color, Numbers;
- stack<int>Stack;
- int node, edge, t1, t2;
- bool dfs(int v)
- {
- if (Color[v] == 1)
- return true;
- if (Color[v] == 2)
- return false;
- Color[v] = 1;
- for (int i = 0;i < g[v].size();i++)
- {
- if (dfs(g[v][i]))
- return true;
- }
- Stack.push(v);
- Color[v] = 2;
- return false;
- }
- bool topsort()
- {
- bool cycle;
- for (int i = 1;i <= node;i++)
- {
- cycle = dfs(i);
- if (cycle)
- return false;
- }
- for (int i = 1;i <= node;i++)
- {
- Numbers[i] = Stack.top();
- Stack.pop();
- }
- return false;
- }
- void create(const int node, const int edge)
- {
- g.resize(node + 1);
- for (int i = 0;i < edge;i++)
- {
- cin >> t1 >> t2;
- if (t1 != t2)
- {
- g[t1].push_back(t2);
- }
- }
- }
- int main()
- {
- cin >> node >> edge;
- Numbers.resize(node + 1);
- create(node, edge);
- for (int i = 0;i < node+1;i++)
- Color.push_back(0);
- topsort();
- if (Numbers[1] !=0)
- {
- for (int i = 1;i <= node;i++)
- cout << Numbers[i] << ' ';
- }
- else cout << -1;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement