Cod sursa(job #2398751)

Utilizator serban24Popovici Serban-Florin serban24 Data 6 aprilie 2019 00:02:06
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define NMAX 50005

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector <int> mv[NMAX];
vector <int> inversa[NMAX];
int viz[NMAX];
int n,m;
deque <int> answer;
queue <int> q;

void BFS(int x){
	int i;

	viz[x]=1;
	q.push(x);
	answer.push_back(x);

	while(!q.empty()){
		x=q.front();
		q.pop();

		for(i=0;i<mv[x].size();i++)
			if(!viz[mv[x][i]]){
				viz[mv[x][i]]=1;
				answer.push_back(mv[x][i]);
				q.push(mv[x][i]);
			}

		for(i=0;i<inversa[x].size();i++)
			if(!viz[inversa[x][i]]){
				viz[inversa[x][i]]=1;
				answer.push_front(inversa[x][i]);
				q.push(inversa[x][i]);
			}
	}
}

int main(){
	int i,x,y;

	fin>>n>>m;

	for(i=1;i<=m;i++){
		fin>>x>>y;
		mv[x].push_back(y);
		inversa[y].push_back(x);
	}

	for(i=1;i<=n;i++)
		if(!viz[i])
			BFS(i);

	while(!answer.empty()){
		fout<<answer.front()<<" ";
		answer.pop_front();
	}

    return 0;
}