Cod sursa(job #1734415)

Utilizator danutbodbodnariuc danut danutbod Data 27 iulie 2016 11:50:23
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#define MAXN 50003
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
int n,m, viz[MAXN], gri[MAXN];//gri[] gradul intern pentru fiecare nod
vector<int> G[MAXN];

void citire_graf(){
    int i,x,y;
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y;
        G[x].push_back(y);gri[y]++;
    }
}

int main(void)
{
   citire_graf();
   int i, j, k;
   //se sfiseaza nodurile (j) care la un moment dat un gradul interior zero. ("radacinile")
   //apoi "stergem" arcele ce ies din (j) decrementam toate nodurile (succesorii directi a lui j)
   //si repetam  in continuare pe  graful ramas.
   for(i = 1; i <= n; i++)    //repet operatia de mai sus de n ori
     {
        for(j = 1; j <= n; j++)    //parcurg nodurile grafului
         if(!viz[j] && gri[j] == 0)  //daca gasesc un nod j nevizitat si de grad intern egal cu 0
          {
            viz[j]=1; fo<<j<<" ";               //afisez j
            for(k=0;k<G[j].size();k++)    //decrementez cu 1 toti succesorii directi a lui j
                gri[G[j][k]]--;
            break ;  // ies !!!
         }
    }

    return 0;
}