Pagini recente » Monitorul de evaluare | Cod sursa (job #172866)
Cod sursa(job #172866)
#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;
}