Cod sursa(job #151514)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 8 martie 2008 11:54:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<string.h>
#define vv 50000

int p[vv],w[vv],q[vv],a[vv][vv],n,m,c,v,o;

void citire()
{
    freopen("sortaret.in","r",stdin);
    scanf("%d%d", &n, &m);
    int x,y,i;
    for(i=0; i<m; i++)
    {
	scanf("%d%d", &x, &y);
	a[x][y]=1;
    }
    c=-1;
    int q;
    for (i=1; i<=n; i++)
    {
        q=0;
        for (int j=1; j<=n; j++)
            if (a[j][i]==1)
            {
                q=1;
                break;
            }
        if (q==0)
        {
            w[++c]=i;
            a[i][0]=1;
        }
    }
    fclose(stdin);
}

void sortare()
{
    o=-1;
    int i;
    while (c>-1)
    {
	v=-1;
	for (i=0; i<=c; i++)
	{
	    for (int j=1; j<=n; j++)
		a[w[i]][j]=0;
	    p[++o]=w[i];
	}
	int b;
	for (i=1; i<=n; i++)
        {
            b=0;
            if (a[i][0]==0)
            {
                for (int j=1; j<=n; j++)
                    if (a[j][i]==1)
                    {
                        b=1;
                        break;
                    }
                if (b==0)
                {
                    q[++v]=i;
                    a[i][0]=1;
                }
            }
        }
        memcpy(w,q,sizeof(q));
        c=v;
    }
}

int main()
{
    citire();
    sortare();
    freopen("sortaret.out","w",stdout);
    for (int i=0; i<=o; i++)
	printf("%d ",p[i]);
    return 0;
}