Cod sursa(job #1010954)

Utilizator sziliMandici Szilard szili Data 15 octombrie 2013 22:50:11
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

vector< vector<int> > v(50001);
vector<int> result;


int visited[50001];
int inDegree[50001];

void dfs(int currentNode){
    visited[currentNode] = 1;

	for (unsigned int i=0; i< v[currentNode].size(); i++){
		if (!visited[v[currentNode][i]]){
            dfs(v[currentNode][i]);
		}
	}

	result.insert(result.begin(), currentNode);

}

int main(){

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	int n,m;

	scanf("%d %d", &n, &m);

	for (int i=0; i<m; i++){
		int a,b;
		scanf("%d %d", &a, &b);

		v[a].push_back(b);
		inDegree[b]++;
	}

    for (int i=1; i<=n; i++){
        if (!visited[i] && inDegree[i] == 0){
            dfs(i);
        }
    }

	for (unsigned int i=0; i<result.size(); i++){
		printf("%d ", result[i]);
	}

	return 0;
}