Cod sursa(job #172866)

Utilizator slayer4uVictor Popescu slayer4u Data 6 aprilie 2008 20:57:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <vector>
using namespace std;

vector <long> graph[65536];

long n, m, i, j, k, a, b, degree[65536], s[65536];

int main()
{
	freopen ("sortaret.in", "rt", stdin);
	freopen ("sortaret.out", "wt", stdout);
	
	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i)
		scanf("%ld %ld", &a, &b), graph[a].push_back(b), ++degree[b];
	
	for (i = 1; i <= n; ++i)
		if (!degree[i]) s[++s[0]] = i;

	for (i = 1; i <= n; ++i)
	{
		vector <long> :: iterator it;  
		k = s[i];
		for(it = graph[k].begin(); it != graph[k].end(); ++it)  
         {  
             degree[*it]--;  
             if(degree[*it] == 0) s[++s[0]] = *it;  // dubious
         }  
/*		for (j = 0; j < graph[k].size(); ++j)
		{
			if (degree[graph[k][j]] == 1)
				s[++s[0]] = graph[k][j];
			else
				--degree[graph[k][j]];
		}*/
	}

	for (i = 1; i <= s[0]; ++i)
			printf("%ld ", s[i]);
	printf("\n");

	return 0;
}