Cod sursa(job #1734440)

Utilizator danutbodbodnariuc danut danutbod Data 27 iulie 2016 12:11:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
// folosesc o coada Q in care introduc pe rand nodurile care au gradul exterior zero
// complexitate O(N+M)
//100p (O(n+m))
#include <fstream>
#include <vector>
#define MAXN 50003
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
int x,i,j,n,m, k,C[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();
for(i=1;i<=n;i++)   //pun initial in coada nodurile de grad 0
    if(gri[i]==0)C[++k]=i;
for(i=1;i<=k;i++)    //parcurg coada
     {
        x=C[i];
        for(j=0;j<G[x].size();j++)
               {
                   gri[G[x][j]]--;  //decrementez cu 1 toti succesorii directi a lui j
                   if(gri[G[x][j]]==0)C[++k]=G[x][j]; //cei ce au gradul 0 se pun in coada

               }
    }
    for(i=1;i<=k;i++)fo<<C[i]<< " ";
    return 0;
}
//#include <fstream>//60p (O(n^2)) timp depasit
//#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;
//}