Cod sursa(job #2798257)

Utilizator CalinCruceanu3576Cruceanu CalinCruceanu3576 Data 11 noiembrie 2021 02:15:20
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin( "sortaret.in" );
ofstream fout( "sortaret.out" );
 
class Graf {
private:

    int N;                   
    vector< vector<int> > adc;
    vector<int> viz, sortate;

    void Dfs(int nod);
      
public:

    Graf(int n);
    void AdaugaMuchie(int x, int y);
	void Sortare(); 
};

void Graf :: Dfs(int nod) {
		int w;
    viz[nod] = 1;
		sortate.push_back(nod);
    for(auto i = 0; i < adc[nod].size(); i++) {
        w = adc[nod][i];
        if(viz[w] == 0)
					Dfs(w);
      	}
}

Graf :: Graf(int n) {
  N = n;
  adc.resize(n + 1);
  viz.resize(n + 1);
}

void Graf :: AdaugaMuchie(int x, int y) {
  adc[x].push_back(y);
} 

void Graf :: Sortare() {
		int i;
    for(i = 1; i <= N; i++)
        viz[i] = 0;
    for(i = 1; i <= N; i++)
         if(viz[i] == 0)
        		Dfs(i);
  	for(auto i = 0; i < sortate.size(); i++)
				fout<<sortate[i]<<" ";

}

int main()
{
    int n, m, x, y, i;
    fin>>n>>m;
    Graf G(n);
    for(i = 1; i <= m; i++) {
        fin >> x >> y;
        G.AdaugaMuchie(x, y);
    }
    G.Sortare();
    return 0;
}