Pagini recente » Cod sursa (job #1805620) | Cod sursa (job #1526183) | Cod sursa (job #531528) | Cod sursa (job #2186857) | Cod sursa (job #979890)
Cod sursa(job #979890)
# include <iostream>
# include <fstream>
# include <vector>
# include <queue>
# include <bitset>
using namespace std;
# define MAXN 50010
# define MAXM 100010
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
vector<pair<int, int> > G[MAXN];
bitset<MAXN> dependent;
int grad[MAXN];
queue<int> coada;
vector <int> grade[MAXN];
void bfs(int nod)
{
grad[nod] = 1;
coada.push(nod);
while (!coada.empty()) {
int nd = coada.front();
coada.pop();
for (int i = 0; i < G[nd].size(); i++) {
if (grad[G[nd][i].first] < grad[nd] + 1) {
grad[G[nd][i].first] = grad[nd] + 1;
coada.push(G[nd][i].first);
}
}
}
}
int main()
{
f >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
f >> x >> y;
G[x].push_back(make_pair(y, i));
dependent[y] = true;
}
for (int i = 1; i <= n; i++) {
if (dependent[i] == false) {
bfs(i);
}
}
for (int i = 1; i <= n; i++) {
grade[grad[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < grade[i].size(); j++) {
g << grade[i][j] << ' ';
}
}
return 0;
}