Cod sursa(job #967866)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 28 iunie 2013 17:30:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<vector>
using namespace std;
struct vecini
{
    vector <int> v;
};
int grad[50009],sol[50009],nr;
bool viz[50009];
vecini g[50009];
void trece(int i)
{
    int j;
    viz[i]=true;
    nr++;
    sol[nr]=i;
    for(j=0;j<g[i].v.size();j++)
    {
        grad[g[i].v[j]]--;
        if(grad[g[i].v[j]]==0)
            trece(g[i].v[j]);
    }
}
int main()
{
    int n,m,i,x,y,j;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        grad[y]++;
        g[x].v.push_back(y);
    }
    nr=0;
    for(i=1;i<=n;i++)
    {
       if(grad[i]==0&&viz[i]==false)
       {
           viz[i]=true;
           nr++;
           sol[nr]=i;
           for(j=0;j<g[i].v.size();j++)
           {
                grad[g[i].v[j]]--;
                if(grad[g[i].v[j]]==0)
                {
                    trece(g[i].v[j]);
                }
           }
       }
    }
    for(i=1;i<=nr;i++)
        printf("%d ",sol[i]);
}