Cod sursa(job #1327066)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 26 ianuarie 2015 12:47:16
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <vector>
std::vector<int> *adj;
int a[50001];
int n,m;
bool in[50001],fol[50001];
int main()
{
    freopen ("sortaret.in","r",stdin);
    freopen ("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    adj=new std::vector<int> [n+1];
    int p1,p2;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d",&p1,&p2);
            in[p2]=1;
            adj[p1].push_back(p2);
    }
    int pos=1;
    for(int i=1;i<=n;i++)
    {
            if(in[i]==0)
            {
                        a[pos]=i;
                        fol[i]=1;
                        pos++;
            }
    }
    for(int i=1;i<pos;i++)
    {
            int len=adj[a[i]].size();
            for(int j=0;j<len;j++)
            {
                    if(fol[adj[a[i]][j]]==0)
                    {
                                            fol[adj[a[i]][j]]=1;
                                            a[pos]=adj[a[i]][j];
                                            pos++;
                    }
            }
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}