Cod sursa(job #789890)

Utilizator ionutz_cnnbIonutz cnnb ionutz_cnnb Data 19 septembrie 2012 18:41:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
/*#include <fstream>
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main()
{
    int m,n,b[100][100],i,j,xi,yi,k,min=777;
    char a[100][100];
    bool mutari;
    ifstream f("cuvinte.in");
    ofstream g("cuvinte.out");
    f>>m>>n;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            f>>a[i][j];
            if(a[i][j]=='L') b[i][j]=0;
            else b[i][j]=-1;
        }
    }
    f>>xi>>yi;
    b[xi][yi]=1;
    for(i=0;i<=m+1;i++) b[i][0]=b[i][n+1]=-1;
	for(j=0;j<=n+1;j++) b[0][j]=b[m+1][j]=-1;
	int contor=0;
	int z=0;
    do
	{
		z=z+1;
		mutari=false;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(b[i][j]==z)
				{
					for(k=0;k<=3;k++)
			        {
						if(b[i+dx[k]][j+dy[k]]==0)
						{
							b[i+dx[k]][j+dy[k]]=z+1;
							mutari=true;
						}
					}
				}
			}
		}
	}while (i!=m&&i!=1&&j!=n&&j!=1&&mutari!=false);
	for(int x=1;x<=m;x++)
	{
	    for(int y=1;y<=n;y++)
	    {
	        g<<b[x][y];
	    }
	    g<<'\n';
	}
    if(i==m-1)
    {
	for(int x=1;x<=n;x++)
	{
	    if(b[m][x]>0)
	    {
	        min=b[m][x];
	        break;
	    }
	}

    }
    if(i==1)
    {
        for(int x=1;x<=n;i++)
        {
	    if(b[1][x]>0)
	    {
	        min=b[1][x];
	        break;
	    }
        }

    }
    if(j==n)
    {
        for(int x=1;x<=m;i++)
        {
	    if(b[x][n]>0)
	    {
	        min=b[x][n];
	        break;
	    }
        }
    }
    if(j==1)
    {
        for(int x=1;x<=m;i++)
        {
	    if(b[x][1]>0)
	    {
	        min=b[x][1];
	        break;
	    }
        }
    }
    g<<min;
    return 0;
}
*/
/*
#include <fstream>
using namespace std;
int n,x[100],n1,n0;
ofstream g("cuvinte.out");
int verif(int k)
{
    int i;
    n0=n1=0;
    for(i=1;i<=k;i++)
    {
        if(x[i]==0) n0++;
        if(x[i]==1) n1++;
    }
    if(n0>n/2) return 0;
    if(n1>n/2) return 0;
    if(n1>n0) return 0;
    return 1;
}
void back(int k)
{
    int i;
    if(k>n)
    {
        for(i=1;i<=n;i++) g<<x[i];
        g<<"\n";
    }
    else
    for(i=0;i<=1;i++)
    {
        x[k]=i;
        if(verif(k)==1)
        {
            back(k+1);
        }
    }
}
int main()
{
    ifstream f("cuvinte.in");
    f>>n;
    back(1);
    return 0;
}
*/
#include<fstream>
using namespace std;
int a[10000][10000],v[10000];
int main()
{
    int n,m,x,y,i,j,contor=0;
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][y]=1;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(a[i][j]==1)
            {
                v[i]++;
            }
        }
    }

    while(contor<n)
    {
        for(i=1;i<=n;i++)
        {
            if(v[i]==0)
            {
                v[i]=-1;
                contor++;
                g<<i;
                for(j=1;j<=n;j++)
                {
                    if(a[j][i]==1) v[j]--;
                }
            }
        }
    }
    return 0;
}