Cod sursa(job #2424451)

Utilizator RaulG99Gioanca Raul RaulG99 Data 23 mai 2019 00:33:57
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50100
#define MMAX 101101
ifstream f("sortaret.in");
ofstream g("sortaret.out");


vector <int> graf[NMAX];
vector <int> sortareTopologica;
int N, M, timp , tata[NMAX], culoare[NMAX], d[NMAX], final[NMAX],viz[NMAX];

void citireGraf()
{
	int i, x, y;
	for (i = 0; i < M; i++)
	{
		f >> x >> y;
		graf[y].push_back(x);
	}
}

void vizita(int nodCurent)
{
	culoare[nodCurent] = 1;
	timp++;
	d[nodCurent] = timp;
	
	
	
	int lim = graf[nodCurent].size();

	for (int i = 0; i < lim; i++)
	{
		int vecin = graf[nodCurent][i];
		if (culoare[i] == 0)
		{
			tata[vecin] = nodCurent;
			vizita(vecin);
		}
	}
	sortareTopologica.push_back(nodCurent);
	culoare[nodCurent] = 2;
	
	timp++;
	final[nodCurent] = timp;
	
}

void DFS(int nod)
{
	viz[nod] = 1;
	int n = graf[nod].size();
	for (int i = 0; i < n; i++)
	{
		int aux = graf[nod][i];
		if (viz[aux] == 0)
			DFS(aux);
	}
	g << nod << " ";
}

void CA()
{
	for (int i = 1; i <= N; i++)
	{
		culoare[i] = 0;
		tata[i] = NULL;
	}
	timp = 0;
	for (int i = 1; i <= N; i++)
	{
		if (culoare[i] == 0)
		{
			vizita(i);
		}
	}
}

int main()
{
	f >> N >> M;
	citireGraf();
	//CA();
	
	for (int i = 1; i <= N; i++)
		if (viz[i] == 0)
			DFS(i);

	/*for (auto &x : sortareTopologica)
		cout << x<<" ";*/
}