Cod sursa(job #929923)

Utilizator Codrin09Sirboiu Codrin Codrin09 Data 27 martie 2013 12:47:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include<fstream>
// reconstitui ordinea prin relatii
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int i, j, pred[100000],v[100000],l,k;
int suc[100000][100000],nr[100000],n,t=0;

int caut(int pred[], int n)
{int i;
for(i=1;i<=n;i++)
   if(pred[i]==0&&v[i])return i;
return 0;
}

int main()
{
    fin>>l>>k;
    while(f>>i>>j)
    {pred[j]++;
     nr[i]++;
     suc[nr[i]][i]=j;
     if(i>n)n=i;
     if(j>n)n=j;
    }
    for(i=1;i<=n;i++)v[i]=1;

    do
    {i=caut(pred,n);
     if(i!=0)if(v[i]){
              g<<i<<' ';t++;
              v[i]=0;
              for(j=1;j<=nr[i];j++)
                 pred[suc[j][i]]--;
              }
}

    while(i!=0&&t<=n);
    if(t<n)g<<"nu avem solutie";
    f.close();
    g.close();
    return 0;
}