9Google AdSense

ACM Problem Solution : Ordering Tasks 10305

#include<stdio.h>

int vertex,indegree1[110],strtop[110];
int graph[110][110];
void topo(int vertex);

int main()
{


    int i,j,edge,p,x,y,kk,ff,rr,pp;
    while(scanf("%d%d",&vertex,&edge)==2)
    {
    if((vertex==0)&&(edge==0))
        break;
    for(ff=1;ff<=vertex;ff++)
        for(rr=1;rr<=vertex;rr++)
            graph[ff][rr]=0;
    for(i=1;i<=edge;i++)
    {
        scanf("%d%d",&x,&y);
        graph[x][y]=1;
    }
    for(kk=1;kk<=vertex;kk++)
    {    indegree1[kk]=0;
        strtop[kk]=0;
    }
    for(i=1;i<=vertex;i++)
        for(j=1;j<=vertex;j++)
            if(graph[j][i]==1)
                indegree1[i]++;
    topo(vertex);
    for(pp=1;pp<=vertex;pp++)
        printf("%d ",strtop[pp]);
    printf("\n");
    }
    return 0;
}
void topo(int vertex)
{
    int l,p,xx,node,top=0,d=0;
    for(l=1;l<=vertex;l++)
        if(indegree1[l]==0)
              strtop[++top]=l;
    while(d!=vertex)
    {
        node=strtop[++d];
        for(xx=1;xx<=vertex;xx++)
            if(graph[node][xx]==1)
            {
                indegree1[xx]=indegree1[xx]-1;
                if(indegree1[xx]==0)
                    strtop[++top]=xx;
            }


    }


}

No comments: