Pagini recente » Cod sursa (job #346615) | Cod sursa (job #259187) | Cod sursa (job #2252974) | Cod sursa (job #3175679) | Cod sursa (job #2789994)
#include <vector>
#include <cstdio>
#include <queue>
#include <cassert>
class Graph
{
public:
Graph(const std::size_t nr_noduri, std::vector<std::vector<int>>&& l_adiacenta)
: nr_noduri(nr_noduri)
, l_adiacenta(std::move(l_adiacenta))
{
}
int componente_conexe() const;
std::vector<int> distante_minime(const int start) const;
std::vector<int> sortare_topologica() const;
std::vector<int> grade_interne() const;
private:
void DFS(std::vector<bool>& visited, int src) const;
void DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
const int src) const;
void BFS(std::vector<int>& dists, int start) const;
private:
std::size_t nr_noduri;
std::vector<std::vector<int>> l_adiacenta;
};
int Graph::componente_conexe() const
{
std::vector<bool> visited(nr_noduri + 1, false);
int res = 0;
for(int node = 1; node <= (int)nr_noduri; ++node)
{
if(!visited[node])
{
++res;
DFS(visited, node);
}
}
return res;
}
std::vector<int> Graph::distante_minime(const int start) const
{
std::vector<int> distante(nr_noduri + 1, -1);
BFS(distante, start);
return distante;
}
std::vector<int> Graph::sortare_topologica() const
{
std::vector<int> sorted;
const auto grd_i = grade_interne();
std::vector<unsigned char> viz(nr_noduri + 1, false);
assert(grd_i.size() == nr_noduri + 1);
assert(viz.size() == nr_noduri + 1);
for(std::size_t node = 1; node <= nr_noduri; ++node)
{
if(grd_i[node] == 0 && !viz[node])
{
DFS_ordine(viz, sorted, node);
}
}
return sorted;
}
std::vector<int> Graph::grade_interne() const
{
std::vector<int> res(nr_noduri + 1, 0);
for(auto& l : l_adiacenta)
{
for(int v : l)
{
++res[v];
}
}
return res;
}
void Graph::DFS(std::vector<bool>& visited, int start) const
{
visited[start] = true;
for(int v : l_adiacenta[start])
{
if(!visited[v])
{
DFS(visited, v);
}
}
}
void Graph::DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
const int src) const
{
res.push_back(src);
visited[src] = true;
for(int v : l_adiacenta[src])
{
if(!visited[v])
{
DFS_ordine(visited, res, v);
}
}
}
void Graph::BFS(std::vector<int>& dists, int start) const
{
std::queue<int> q;
q.push(start);
dists[start] = 0;
while(!q.empty())
{
const auto node = q.front();
q.pop();
for(int v : l_adiacenta[node])
{
if(dists[v] == -1)
{
q.push(v);
dists[v] = dists[node] + 1;
}
}
}
}
int main()
{
int N, M;
scanf("%d %d", &N, &M);
std::vector<std::vector<int>> list(N + 1);
for(int i = 0; i < M; ++i)
{
int a,b;
scanf("%d %d", &a, &b);
list[a].push_back(b);
}
const Graph g(N, std::move(list));
const auto noduri_sortate = g.sortare_topologica();
for(int v : noduri_sortate)
{
printf("%d ", v);
}
putchar('\n');
}
static int redir = []()
{
std::freopen("sortaret.in", "r", stdin);
std::freopen("sortaret.out", "w", stdout);
return 0;
}();