Cod sursa(job #2844086)
Utilizator | Nicula Ionut icnsr | Data | 3 februarie 2022 18:56:36 |
---|---|---|---|
Problema | Sortare topologica | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.13 kb |
#include <cstdio>
#include <vector>
#include <queue>
static int N, M;
static std::vector<std::vector<int>> adj;
static std::vector<int> in_degree;
int main()
{
scanf("%d %d", &N, &M);
adj.resize(N + 1);
in_degree.resize(N + 1);
for(int i = 0; i < M; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
++in_degree[v];
}
std::queue<int> q;
for(int i = 1; i <= N; ++i)
{
if(in_degree[i] == 0)
{
q.push(i);
}
}
std::vector<char> visited(N + 1, false);
while(!q.empty())
{
const int u = q.front();
q.pop();
visited[u] = true;
printf("%d ", u);
for(const int v : adj[u])
{
--in_degree[v];
if(in_degree[v] == 0)
{
q.push(v);
}
}
}
puts("");
}