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

Exemplu

topsort.in

topsort.out

7 6 3 4 1 2 5

Explicație

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema TopSort:

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <cstring>
#define NN 100001
using namespace std;



fstream fin("topsort.in", ios::in), fout("topsort.out", ios::out);

int n, v[NN];

list<int> F;
vector<int> G[NN];

void dfs(int x){
    v[x] = 1;
    for(vector<int>::iterator I = G[x].begin(); I < G[x].end() ; I++)
        if(v[*I] == 0)
            dfs(*I);
    F.push_front(x);
}

int main(){
    fin >> n;
    int m;
    for(fin >> m ; m ; m --)
    {
        int x , y;
        fin >>x >> y;
        G[x].push_back(y);
    }
    for(int i = 1 ; i <= n ; i++)
        if(v[i] == 0)
            dfs(i);
    for(list<int>::iterator x = F.begin() ; x != F.end() ; x ++)
        fout << *x << " ";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1861 TopSort

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1861 TopSort de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1861 TopSort