Cod sursa(job #2150937)

Utilizator greelioGreenio Greely greelio Data 3 martie 2018 21:47:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<bits/stdc++.h>
#define NMAX 50005

using namespace std;

vector<int>V[NMAX];
queue<int>Q1;
vector<int>Q;
bool viz[NMAX];
int n,m;

void DFS(int x) {
	viz[x]=1;
	for (int i=0; i<V[x].size(); i++) {
		if (!viz[V[x][i]]) DFS(V[x][i]);
	}
	Q.push_back(x);
}

int main() {
	ifstream cin("sortaret.in");
	ofstream cout("sortaret.out");
	cin>>n>>m;
	
	for (int i=1; i<=m; i++) {
		int x,y; cin>>x>>y; viz[y]=1;
		V[x].push_back(y);
	}
	
	int p=1;
	for (int i=1; i<=n; i++) {
		if (!viz[i]) Q1.push(i);
		viz[i]=0;
	}
	while (Q1.size()) { 
		p=Q1.front(); Q1.pop();
		if (!viz[p]) DFS(p);
	}
	
	while (Q.size()) {
		cout<<Q.back()<<" "; Q.pop_back();
	}
	
	return 0;
}