Mai intai trebuie sa te autentifici.

Cod sursa(job #2691568)

Utilizator Silviu45Dinca Silviu Silviu45 Data 29 decembrie 2020 12:04:04
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
unsigned int N,M,x,y;
vector< vector<unsigned int> > adj;
stack<unsigned int> sortare_topo;
vector<char> visited;

void Read(){
	fin >> N >> M; adj = vector< vector<unsigned int> >(N+1);//aloc N linii 
	visited = vector<char>(N+1);
	while(fin >> x >> y){
		adj[x].push_back(y);
	}
}

void DFS(unsigned int nod){
	visited[nod] = '1';
	for(int n = 0; n < adj[nod].size(); n++)
		if(visited[n]=='0')
			DFS(n);
	//inserez in lista 
	sortare_topo.push(nod);
}

void ConstructSort(){
	for(int i = 1; i <= N; i++)
		visited[i] = '0';
	for(int i = 1; i <= N; i++){
		if(visited[i] == '0')
			DFS(i);
	}
}

void Display_Sort(){
	while(!sortare_topo.empty()){
		fout << sortare_topo.top() << " ";
		sortare_topo.pop();
	}
}

int main(){
	Read();
	ConstructSort();
	Display_Sort();
	/*for(int i = 1; i <= N; i++){
		for(int j = 0; j < adj[i].size(); j++){
			cout << adj[i][j] << " ";
		}
		cout << endl;
	}*/

	return 0;
}