Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void dfs(long long v, vector<long long>* gr, vector<bool>& used, vector<long long>& an)
- {
- used[v] = true;
- for (long long i = 0; i < gr[v].size(); i++)
- {
- long long flag = gr[v][i];
- if (!used[flag])
- dfs(flag, gr, used, an);
- }
- an.push_back(v + 1);
- }
- void topSort(long long n, vector<long long>* gr, vector<bool>& used, vector<long long>& an)
- {
- for (long long i = 0; i < n; i++)
- used[i] = false;
- for (long long i = 0; i < n; i++)
- if (!used[i])
- dfs(i, gr, used, an);
- reverse(an.begin(), an.end());
- }
- bool checky(long long v, long long& checkys, vector<long long>* gr, vector<long long>& color)
- {
- color[v] = 1;
- for (size_t i = 0; i < gr[v].size(); i++)
- {
- long long flag = gr[v][i];
- if (color[flag] == 0)
- {
- if (checky(flag, checkys, gr, color))
- return true;
- }
- else if (color[flag] == 1)
- {
- checkys = flag;
- return true;
- }
- }
- color[v] = 2;
- return false;
- }
- int main()
- {
- long long n, m;
- cin >> n >> m;
- long long a, b;
- vector<long long> gr[n + 1];
- vector<bool> used(n);
- vector<long long> an;
- vector<long long> color(n, 0);
- long long checkys = -1;
- for (long long i = 0; i < m; i++)
- {
- cin >> a >> b;
- gr[a - 1].push_back(b - 1);
- }
- for (long long i = 0; i < n; i++)
- {
- if (checky(i, checkys, gr, color))
- break;
- }
- if (checkys != -1)
- cout << "-1";
- else
- {
- topSort(n, gr, used, an);
- for (long long i = 0; i < an.size(); i++)
- {
- cout << an[i] << " ";
- }
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement