Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <iostream>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <queue>
- using namespace std;
- vector <bool> used;
- vector <bool> colour;
- int time = 0;
- vector <int> tin;
- vector <int> tout;
- vector <int> ans;
- void dfs(int v, vector <vector<int>> & a, bool col)
- {
- tin[v] = ++time;
- used[v] = true;
- colour[v] = !col;
- for (auto i = a[v].begin(); i != a[v].end(); i++)
- if (!used[*i])
- dfs(*i, a, !col);
- tout[v] = ++time;
- ans.push_back(v);
- }
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n;
- cin >> n;
- vector <vector <int>> g(n, vector <int>(n));
- vector <vector <int>> a(n);
- used.resize(n);
- colour.resize(n);
- tin.resize(n);
- tout.resize(n);
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> g[i][j];
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- {
- if (g[i][j] == 1)
- a[i].push_back(j);
- }
- for (int i = 0; i < n; i++)
- if (!used[i])
- dfs(i, a, false);
- /*
- for (int i = 0; i < n; i++)
- cout << tin[i] << ' ';
- cout << endl;
- for (int i = 0; i < n; i++)
- cout << tout[i] << ' ';
- cout << endl;
- */
- reverse(ans.begin(), ans.end());
- for (int i = 0; i < ans.size(); i++)
- cout << ans[i] + 1 << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement