Pagini recente » Cod sursa (job #1091137) | Cod sursa (job #394801) | Cod sursa (job #2822611) | Cod sursa (job #224904) | Cod sursa (job #990726)
Cod sursa(job #990726)
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
int used[50001],n,m,degree[50001];
vector<int> lv[50001];
pair <int,int> vertx[200000];
void get_Data()
{
scanf("%d%d",&n,&m);
int x,y,i;
for(i = 1; i <= m; ++i){
scanf("%d%d", &x, &y);
vertx[ i ] = make_pair(x,y);
}
sort(vertx+1,vertx+m+1);
for(i = 1; i <= m; ++i)
if(vertx[ i ].x != vertx[ i ].y &&
(vertx[ i - 1 ].x != vertx[ i ].x || vertx[ i - 1 ].y != vertx[ i ].y)){
lv[vertx[i].x].push_back(vertx[i].y);
++degree[vertx[i].y];
}
}
void Topological()
{
int i,j;
vector<int> ::iterator it;
queue <int> Q;
for(i = 1; i <= n; ++i)
if(!degree[ i ])
Q.push( i );
while(!Q.empty()){
j = Q.front();Q.pop();
printf("%d ",j);
used[ j ] = 1;
for(it = lv[j].begin(); it != lv[ j ].end(); ++it){
--degree[ *it ];
if(degree[ *it ] == 0 && !used[ *it ])
Q.push( *it );
}
}
}
int main()
{
freopen ("sortaret.in", "r", stdin);
freopen ("sortaret.out", "w", stdout);
get_Data();
Topological();
return 0;
}