Cod sursa(job #2054285)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 1 noiembrie 2017 20:50:17
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

bool viz[5005];
int a[5005][5005];
int solutie[5005];
bool adaugat[5005];
int grad_ext[5005];
int contor = 1;
int N, M;

void DFS(int nc)
{
    int i;
    viz[nc] = 1;
    for(i = 1;i <= N; i++)
        if(!viz[i] and a[nc][i]) {
            
            adaugat[i] = 1;
    		solutie[++contor] = i;
    		DFS(i);
        }
    
}
int main()
{
	f >> N >> M;
	for(int i = 1; i <= M; ++i) {
		int x, y;
		f >> x >> y;
		a[x][y] = 1;
		grad_ext[y]++;
	}

	
	for(int i = 1; i <= N; ++i) {
		if(grad_ext[i] == 0) {
			adaugat[i] = 1;
			solutie[1] = i;
			DFS(i);
			break;
		}
	}

	for(int i = 1; i <= N; ++i) {
		g << solutie[i] << " ";
	}

}