Cod sursa(job #929920)

Utilizator Codrin09Sirboiu Codrin Codrin09 Data 27 martie 2013 12:45:31
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include<fstream>
// reconstitui ordinea prin relatii
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int i, j, pred[100],v[100];
int suc[100][100],nr[100],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()
{
    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;
}