Question

VA ROG MULT!!!
problema #1861 topsort pbinfo

Cerința
Se dă un graf orientat aciclic cu N noduri numerotate de la 1 la N. Să se realizeze o sortare topologică a nodurilor.

Date de intrare
Fișierul de intrare topsort.in conține pe prima linie numerele N M, reprezentând numărul de noduri și numărul de arce din graf, iar pe următoarele M linii câte o pereche de noduri i j, cu semnificația că în graf există arcul (i j).

Date de ieșire
Fișierul de ieșire topsort.out va conține pe prima linie cele N noduri ale grafului, separate prin exact un spațiu, în ordinea dată de sortarea topologică.

Restricții și precizări
1 ≤ N ≤ 100000
1 ≤ M ≤ 400000

Answer 1

Răspuns:

#include <bits/stdc++.h>

#define DIM 100010

using namespace std;

ifstream fin("topsort.in");

ofstream fout("topsort.out");

int n,m,i,x,y,k,r,t[DIM],sol[DIM];

vector<int> L[DIM];

bitset<DIM> f;

void dfs(int nod) {

   f[nod]=1;

   for (int i=0;i<L[nod].size();i++) {

       int vecin=L[nod][i];

       if (f[vecin]==0)

           dfs(vecin);

   }

   sol[k++]=nod;

}

int main() {

   fin>>n>>m;

   for (i=1;i<=m;i++) {

       fin>>x>>y;

       L[x].push_back(y);

       t[y]=x;

   }

   for (i=1;i<=n;i++)

       if (f[i]==0)

           dfs(i);

   while (k--)

       fout<<sol[k]<<" ";

   return 0;

}

Explicație: