Pagini recente » Cod sursa (job #2853725) | Cod sursa (job #2027812) | Cod sursa (job #2848580) | Cod sursa (job #2116370) | Cod sursa (job #2720368)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define IPair pair<int,int>
int N, M;
int main()
{
ifstream f("sortaret.in");
ofstream g("sortaret.out");
// Program
f >> N >> M;
vector<vector<int>> links(N+1, vector<int>());
vector<int> levelOfNode(N + 1, -1);
vector<bool> topLevel(N+1,true);
for (int i = 0; i < M; i++)
{
int x, y;
f >> x >> y;
links[x].push_back(y);
topLevel[y] = false;
}
for (int i = 1; i <= N; i++)
{
if (topLevel[i])
{
links[0].push_back(i);
}
}
//delete &topLevel;
queue<IPair> q;
q.push(make_pair(0,0));
int maxNode = 0;
while (!q.empty())
{
IPair pr = q.front();
q.pop();
int node = pr.first;
int nodeLevel = pr.second;
if (levelOfNode[node] < nodeLevel)
{
levelOfNode[node] = nodeLevel;
maxNode = max(maxNode, nodeLevel);
}
for (auto it = links[node].begin(); it != links[node].end(); it++)
{
q.push(make_pair(*it, nodeLevel + 1));
}
}
vector<vector<int>> levels(maxNode+1,vector<int>());
for (int i = 1; i <= N; i++)
{
levels[levelOfNode[i]].push_back(i);
}
for (auto it = levels.begin() + 1; it != levels.end(); it++)
{
for (auto jt = (*it).begin(); jt != (*it).end(); jt++)
{
g << *jt << " ";
}
}
// Exit
f.close();
g.close();
return 0;
}