Cod sursa(job #742045)

Utilizator dbalutaDaniel Baluta dbaluta Data 27 aprilie 2012 23:00:42
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MAX_VERTICES 50000
int N, M;

/* vertices are numbered starting with 1 */
vector<int> graph[MAX_VERTICES + 1];

/* number of edges leaving from a node */
int degree[MAX_VERTICES + 1];

/* simulate node removal */
int visited[MAX_VERTICES + 1];

void solve(void) {
	int i, m, n, j, k;
	
	scanf("%d %d", &N, &M);
	
	for (i = 0; i < M; i++) {
		scanf("%d %d", &m, &n);
		graph[m].push_back(n);
		degree[n]++;
	}

	/* find a zero node degree, print it -> go back to step 1 */
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			if (!visited[j] && !degree[j]) {
				printf("%d ", j);
				visited[j] = 1;
				for (k = 0; k < graph[j].size(); k++) 
					degree[graph[j][k]]--;
				break;
			}
		}
	}
}			
		
		
int main(void)
{

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

	solve();

	return 0;
}