Cod sursa(job #1734444)

Utilizator danutbodbodnariuc danut danutbod Data 27 iulie 2016 12:34:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.24 kb
//var III
// parcurgere in adancime pentru a calcula timpii de terminare pentru fiecare varf
// 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,viz[MAXN], sol[MAXN];
vector<int> G[MAXN];
void DF(int nod){
int i;
viz[nod]=1;
for(i=0;i<G[nod].size();i++)
    if(viz[G[nod][i]]==0)DF(G[nod][i]);
sol[++k]=nod;
}

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

int main(void)
{
citire_graf();

for(i=1;i<=n;i++)
    if(viz[i]==0)DF(i);

for(i=k;i>=1;i--)fo<<sol[i]<< " ";
//for(i=1;i<=n;i++) //afis liste de adiacenta
//{
//    fo<<i<<" -> ";
//    for(j=0;j<G[i].size();j++)fo<<G[i][j]<<" ";
//    fo<<endl;
//}
    return 0;
}
////var II
//// 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;
//}
//var I
////60p (O(n^2)) timp depasit
//#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;
//}