Mai intai trebuie sa te autentifici.
Cod sursa(job #2439775)
Utilizator | Data | 16 iulie 2019 20:24:15 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.1 kb |
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define int ll
#define sz size()
#define x first
#define y second
#define pd pair <long double, long double>
#define pii pair <pi, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
const ll nmax=5e4+2;
int n, m, color[100002];
bool ctrl=1;
vector <int> g[50001];
vector <int> ans;
int dfs(int node){
color[node]=1;
for(int i: g[node]){
if(color[i]==0){
dfs(i);
}
else if(color[i]==1) ctrl=0;
}
color[node]=2;
ans.pb(node);
}
int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
cin>>n>>m;
for(int i=1; i<=m; i++){
int x, y;
cin>>x>>y;
g[x].pb(y);
}
for(int i=1; i<=n; i++){
if(color[i]==0) dfs(i);
}
//if(ctrl==0) cout<<"xd";
reverse(ans.begin(), ans.end());
for(int i: ans) cout<<i<<" ";
}