Pagini recente » Monitorul de evaluare | Cod sursa (job #1824066) | Cod sursa (job #2951063) | Cod sursa (job #246851) | Cod sursa (job #199517)
Cod sursa(job #199517)
//@RomoCoder
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
set<pair<int, int> > G; //<grad, nod>
int GG[60001];
vector<vector<int> > V;
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int N, M;
scanf("%d %d", &N, &M);
V.resize(N+3);
while (M--)
{
int a, b;
scanf("%d %d", &a, &b);
++GG[b]; //gradu creste
V[a].push_back(b);
// pair<int, int> nod(GG[b]-1, b);
// if (G.find(nod) != G.end())
// {
// G.erase(G.find(nod));
// }
//nod.first = GG[b];
//G.insert(nod);
}
for ( int i = 1; i <= N; ++i) G.insert(make_pair(GG[i], i));
while (!G.empty())
{
pair<int, int> nod;
nod = *G.begin();
//erase it
G.erase(G.begin());
printf("%d ", nod.second);
//update it
for (int i = 0; i < V[nod.second].size(); ++i) {
int tipa = V[nod.second][i];
GG[tipa]--;
pair<int, int> nod2(GG[tipa]+1, tipa);
if (G.find(nod2) != G.end()) {
G.erase(G.find(nod2));
}
nod2.first = GG[tipa];
G.insert(nod2);
}
V[nod.second].resize(0);
}
return 0;
}
//RomoCoder in Action Again