Pagini recente » Istoria paginii runda/285600 | Cod sursa (job #2520014) | Cod sursa (job #1827632) | Cod sursa (job #1899450) | Cod sursa (job #681868)
Cod sursa(job #681868)
using namespace std;
#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(ll (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (ll (i)=0;(i)<(ll)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))
#define IN "sortaret.in"
#define OUT "sortaret.out"
//#define ONLINE_JUDGE
static const int MAX_NODES = 50100;
static const int MAX_EDGES = 100000;
int nodeCount;
int edgeCount;
int incoming[MAX_NODES];
queue<int> noParentNodes;
list<int> neighbors[MAX_NODES];
list<int> sortedNodes;
void buildGraph ()
{
int x, y;
for (int i = 0; i < edgeCount; i++)
{
cin >> x >> y;
neighbors[x].push_back(y);
incoming[y]++;
}
}
void topSort()
{
for (int i = 1; i <= nodeCount; i++)
{
if (incoming[i] == 0)
{
noParentNodes.push(i);
}
}
while (!noParentNodes.empty())
{
int node = noParentNodes.front();
noParentNodes.pop();
list<int>::iterator it;
list<int>* neighs = &neighbors[node];
for (it = neighs->begin(); it != neighs->end(); it++)
{
if (incoming[*it] > 0)
{
incoming[*it]--;
if (incoming[*it] == 0)
{
noParentNodes.push(*it);
}
}
}
sortedNodes.push_back(node);
}
list<int>::iterator it;
for (it = sortedNodes.begin(); it != sortedNodes.end(); it++)
{
cout << *it << " ";
}
}
vector<list<int>*>* graph;
void solve(int test) {
cin >> nodeCount;
cin >> edgeCount;
buildGraph();
topSort();
}
int main() {
#ifndef ONLINE_JUDGE
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
#endif
solve(0);
return 0;
}