Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_DEPRECATE
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <string>
- #include <cstring>
- #include <sstream>
- #include <set>
- #include <map>
- #include <queue>
- #include <memory.h>
- #include <ctime>
- using namespace std;
- #pragma comment(linker, "/STACK:128000000")
- typedef pair<int, int> pii;
- typedef long long int64;
- typedef pair<int64, int64> pii64;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<pii> vpii;
- typedef vector<vpii> vvpii;
- typedef pair<int,pii> piii;
- typedef pair<int64,pii> piii64;
- typedef pair<pii,pii> piiii;
- #define y1 dsjfksdj_fks
- #define y2 alksaad_sa
- #define y0 _sdkfsjfs__
- #define tm _dskfjskdfjksdf
- int n, m;
- vvi g;
- vector <int> e;
- vector <int> was;
- vector <int> used;
- vector <int> cur;
- vector <int> res;
- priority_queue <int> q;
- inline void init()
- {
- scanf("%d%d", &n, &m);
- g.resize(n);
- was.assign(n, 0);
- e.assign(n, 0);
- used.assign(n, 0);
- int x, y;
- for (int i = 0; i < m; ++i)
- {
- scanf("%d%d", &x, &y);
- --x, --y;
- g[y].push_back(x);
- }
- for (int i = 0; i < n; ++i)
- if (g[i].size())
- sort(g[i].begin(), g[i].end());
- }
- void dfs(int x)
- {
- used[x] = 1;
- int k = (int)g[x].size();
- for (int i = 0; i < k; ++i)
- {
- int y = g[x][i];
- if (was[y]) continue;
- ++e[y];
- if (used[y]) continue;
- dfs(y);
- }
- }
- inline void qadd(int x)
- {
- q.push(x);
- }
- int main()
- {
- //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- init();
- for (int i = 0; i < n; ++i)
- {
- if (was[i]) continue;
- dfs(i);
- qadd(i);
- while (!q.empty())
- {
- int x = q.top();
- was[x] = 1;
- q.pop();
- cur.push_back(x);
- int k = (int)g[x].size();
- for (int j = 0; j < k; ++j)
- {
- int y = g[x][j];
- --e[y];
- if (e[y]) continue;
- qadd(y);
- }
- }
- while (cur.size())
- {
- res.push_back(cur.back());
- cur.pop_back();
- }
- }
- for (int i = 0; i < n; ++i)
- printf("%d ", res[i] + 1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment