Cod sursa(job #2798728)

Utilizator CalinCruceanu3576Cruceanu CalinCruceanu3576 Data 11 noiembrie 2021 19:34:10
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 i, w;
    viz[nod] = 1;
    for(i = 0; i < adc[nod].size(); i++) {
        w = adc[nod][i];
        if(viz[w] == 0)
					Dfs(w);
      	}
    sortate.push_back(nod);
}
 
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(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;
}