Pagini recente » Cod sursa (job #1432447) | Cod sursa (job #3217121) | Cod sursa (job #1432274) | Cod sursa (job #1420482) | Cod sursa (job #1411530)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using Graph = std::vector<std::vector<int>>;
using Pq = std::priority_queue<std::pair<int, int>>;
void dfs(const Graph &G, int node, std::vector<bool> &visited, Pq &q, int &time)
{
visited[node] = true;
for (auto &neigh : G[node])
if (!visited[neigh])
dfs(G, neigh, visited, q, ++time);
q.emplace(++time, node);
}
Pq get_finish_times(const Graph &G)
{
Pq q;
std::vector<bool> visited(G.size(), false);
int time = 0;
for (auto i = 0u; i < G.size(); ++i)
if (!visited[i])
dfs(G, i, visited, q, ++time);
return q;
}
Graph reverse(const Graph &G)
{
Graph rvs(G.size());
for (auto i = 0u; i < G.size(); ++i)
for (auto &neigh : G[i])
rvs[neigh].push_back(i);
return rvs;
}
void dfs_rev(const Graph &G,
int node,
Pq &q,
std::vector<bool> &visited,
std::vector<std::vector<int>> &ret)
{
visited[node] = true;
ret.back().push_back(node);
q.pop();
for (auto &neigh : G[node])
if (!visited[neigh])
dfs_rev(G, neigh, q, visited, ret);
}
std::vector<std::vector<int>> get_comps(Graph &&G, Pq &&q)
{
std::vector<bool> visited(G.size(), false);
std::vector<std::vector<int>> ret;
while (!q.empty()) {
ret.push_back(std::vector<int>());
dfs_rev(G, q.top().second, q, visited, ret);
}
return ret;
}
int main()
{
std::ifstream fin{"ctc.in"};
std::ofstream fout{"ctc.out"};
int N, M;
fin >> N >> M;
Graph G(N);
for (auto i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
G[x - 1].push_back(y - 1);
}
auto ret = get_comps(reverse(G), get_finish_times(G));
fout << ret.size() << '\n';
for (auto &comp : ret) {
for (auto &elem : comp)
fout << elem + 1 << ' ';
fout << '\n';
}
return 0;
}