Pagini recente » Cod sursa (job #926697) | Cod sursa (job #1843935) | Cod sursa (job #2660622) | Cod sursa (job #3256209) | Cod sursa (job #1893542)
#include <algorithm>
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
typedef vector<vector<int>> Graph;
void Dfs(const Graph &g, int node, vector<bool> &vis, vector<int> &ord)
{
vis[node] = true;
for (int i : g[node]) {
if (!vis[i]) {
Dfs(g, i, vis, ord);
}
}
ord.push_back(node);
}
vector<int> TopoSort(const Graph &g)
{
vector<bool> visited(g.size(), false);
vector<int> order;
for (unsigned i = 0; i < g.size(); ++i) {
if (!visited[i]) {
Dfs(g, i, visited, order);
}
}
return order;
}
void Fill(const Graph &g, vector<int> &colours, int node, int col)
{
colours[node] = col;
for (int i : g[node]) {
if (colours[i] == -1) {
Fill(g, colours, i, col);
}
}
}
vector<vector<int>> FindComponents(const Graph &norm, const Graph &rev)
{
auto order = TopoSort(norm);
vector<int> colours(norm.size(), -1);
int ncolours = 0;
for (int i = order.size() - 1; i >= 0; --i) {
if (colours[order[i]] == -1) {
Fill(rev, colours, order[i], ncolours);
++ncolours;
}
}
vector<vector<int>> components(ncolours);
for (unsigned i = 0; i < colours.size(); ++i) {
components[colours[i]].push_back(i);
}
return components;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
Graph normal_graph(n);
Graph reversed_graph(n);
while (m--) {
int x, y;
fin >> x >> y;
normal_graph[x - 1].push_back(y - 1);
reversed_graph[y - 1].push_back(x - 1);
}
auto comp = FindComponents(normal_graph, reversed_graph);
fout << comp.size() << "\n";
for (const auto &c : comp) {
for (int i : c) {
fout << i + 1 << " ";
}
fout << "\n";
}
return 0;
}