Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl '\n'
- int n,m;
- vector<int> G2[200002];
- int OUTDEG[222222];
- bool u[222222];
- int main( void ) {
- cin.tie( 0 ); cin.sync_with_stdio( 0 );
- set<pair<int,int> > S;
- cin >> n >> m;
- for (int i = 0; i < m; i++) {
- int a,b;
- cin >> a >> b;
- a--,b--;
- if (S.find(make_pair(a,b)) != S.end()) continue;
- S.insert(make_pair(a,b));
- G2[b].push_back(a);
- OUTDEG[a]++;
- }
- vector<int> R;
- int cur = 0;
- while (cur < n) {
- priority_queue<int> Q;
- vector<int> RR;
- Q.push(cur);
- while (Q.size()) {
- int v = Q.top();
- Q.pop();
- RR.push_back(v);
- for (int i = 0; i < (int)G2[v].size(); i++) {
- int vv = G2[v][i];
- if (u[vv]) continue;
- OUTDEG[vv]--;
- if (OUTDEG[vv] == 0) {
- Q.push(vv);
- }
- }
- u[v] = 1;
- }
- for (int i = (int)RR.size()-1; i >= 0; i--) {
- R.push_back(RR[i]);
- }
- while (u[cur]) cur++;
- }
- for (int i = 0; i < n; i++) {
- cout << R[i]+1 << " " ;
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment