Cod sursa(job #2129658)

Utilizator AndreiBaraianAndrei Baraian AndreiBaraian Data 12 februarie 2018 23:10:55
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define NMAX 50000
#define MMAX 100000
#define WHITE 0
#define GREY 1
#define BLACK 2

vector<int> G[NMAX];
queue<int> resultList;
int colors[NMAX];
int n, m;

void DFS_Visit(int u)
{
	colors[u] = GREY;
	for (int i = 0; i < G[u].size(); i++)
	{
		if (G[u].at(i) == WHITE)
			DFS_Visit(i);
	}
	colors[u] = BLACK;
	resultList.push(u);
}

void DFS()
{
	for (int i = 1; i <= n; i++)
	{
		if (colors[i] == WHITE)
			DFS_Visit(i);
	}
}

int main()
{
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		f >> x >> y;
		G[x].push_back(y);
	}
	f.close();
	DFS();
	for (int i = 0; i < resultList.size(); i++)
	{
		g << resultList.front() << " ";
		resultList.pop();
	}
	g.close();
	return 0;
}