Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma optimization_level 3
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <functional>
- #include <set>
- #include <map>
- #include <math.h>
- #include <cmath>
- #include <string>
- //#include <random>
- //#include <unordered_set>
- //#include <unordered_map>
- #include <bitset>
- #include <string.h>
- #include <stack>
- #include <assert.h>
- #include <list>
- #include <time.h>
- //#include <tuple>
- #include <memory>
- //#include <chrono>
- using namespace std;
- //
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- //#define cin in
- //#define cout out
- #define ll long long
- #define db double
- #define ld long double
- #define uset unordered_set
- #define umap unordered_map
- #define ms multiset
- #define pb push_back
- //#define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define ull unsigned long long
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define pdd pair<ld, ld>
- #define pnn pair<Node*, Node*>
- #define uid uniform_int_distribution
- #define PI acos(-1.0)
- //#define sort(a, b) sort(a.begin(), a.end(), b())
- //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- ifstream in("input.txt");
- ofstream out("output.txt");
- const int MAX_N = 2e5;
- vector<int> pr[MAX_N];
- int n, m;
- int out_degr[MAX_N];
- bool used[MAX_N]; // is already in ans
- void input() {
- cin >> n >> m;
- vector<pii> edges(m);
- for (int i = 0; i < m; ++i) {
- int a, b;
- cin >> a >> b;
- edges[i] = make_pair(a-1, b-1);
- }
- sort(edges.begin(), edges.end());
- edges.resize(unique(edges.begin(), edges.end()) - edges.begin());
- m = edges.size();
- for (int i = 0; i < m; ++i) {
- int a = edges[i].first, b = edges[i].second;
- pr[b].push_back(a);
- }
- }
- // проход по предкам
- void dfs(int v, int& cnt) {
- for (int _ = 0; _ < pr[v].size(); ++_) {
- int p = pr[v][_];
- if (!used[p]) {
- cnt += (out_degr[p] == 0); // первый раз пришли в вершину
- ++out_degr[p];
- dfs(p, cnt);
- }
- }
- }
- vector<int> ans;
- // в каждой компоненте макс. вершина с исх. степенью 0
- void solve(int v0, int& ins_pos) {
- int pos = ins_pos;
- dfs(v0, pos);
- ins_pos = pos + 1;
- // pos - начиная с какого ставим
- // ins_pos - первый свободный в ans
- priority_queue<int> pq;
- pq.push(v0);
- while (!pq.empty()) {
- int v = pq.top();
- pq.pop();
- for (int _ = 0; _ < pr[v].size(); ++_) {
- int p = pr[v][_];
- if (!used[p] && --out_degr[p] == 0)
- pq.push(p);
- }
- ans[pos--] = v;
- used[v] = 1;
- }
- }
- int main() {
- input();
- ans.resize(n);
- int pos = 0;
- memset(out_degr, 0, sizeof(out_degr));
- memset(used, 0, sizeof(used));
- for (int v = 0; v < n; ++v) {
- if (!used[v])
- solve(v, pos);
- }
- for (int _ = 0; _ < n; ++_)
- cout << ans[_] + 1 << ' ';
- }
Advertisement
Add Comment
Please, Sign In to add comment