Cod sursa(job #2265599)

Utilizator petru123456789Petru B petru123456789 Data 21 octombrie 2018 14:40:16
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;
vector<int> v[50005],b[50005];
bool viz[50005];
int n,m,r,x,y,ok,w;
void dfs(int q)
{
    if(ok==0)
        {
            w=q;
            b[w].push_back(w);
        }
    ok=1;
    viz[q]=1;
    for(int i=0; i<v[q].size(); i++)
    {
        r=v[q][i];
        if(viz[r]==0)
            {
                b[w].push_back(r);
                dfs(r);
            }
    }
}
int main()
{
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        v[x].push_back(y);

    }
    for(int i=1;i<=n;i++)
    {

        ok=0;
        if(viz[i]==0)
        {
            dfs(i);
        }

    }
    for(int i=n;i>=1;i--)
    {
        if(b[i].size()>0)
        {
            //out<<i<<' ';

            for(int j=0;j<b[i].size();j++)
            {
                out<<b[i][j]<<' ';
            }
        }
    }
}