Cod sursa(job #1691757)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 19 aprilie 2016 12:39:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
// Template v2
#define pb push_back
#define mp make_pair
#define first x
#define second y
#define l(x) x<<1
#define r(x) x<<1 | 1
#define lsb(x) x & -x
#include<fstream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<string.h>
#include <bitset>
using namespace std;
  
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PKK;
// primes less than 100
const int PRIM[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
const int CMAX = 10005;
const int MOD = 1000000007;
const int NMAX = 50069;
const int LOGMAX = log2(250666)+8;
const int INF16 = 320000;
const int INF = 2*1e9 + 6661369;
const LL INF64 = LL(1e18);
const LD EPS = 1e-9, PI = acos(-1.0);
const int dx[]={-1,1,0,0};
const int dy[]={0,0,1,-1};

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

int viz[NMAX];
int toposort[NMAX], k;
VI G[NMAX];
int n,m;

void dfs(int v)
{
    viz[v]=1;
    for(auto w:G[v])
        if(!viz[w])
            dfs(w);
    toposort[++k]=v;
}
int a,b;
void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        cin>>a>>b;
        G[a].pb(b);
    }
    for(int i=1; i<=n; ++i)
        if(!viz[i])
            dfs(i);
    for(int i=k; i>=1; --i)
        cout<<toposort[i]<<" ";
}
 
int main(){
    //cout<<setprecision(4)<<fixed;
    read();
    return 0;
}