Pagini recente » Cod sursa (job #523427) | Cod sursa (job #1440479) | Cod sursa (job #427250) | Cod sursa (job #672137) | Cod sursa (job #3248750)
#include <bits/stdc++.h>
using namespace std;
vector <int> graph[200005], revGraph[200005];
vector <int> depOrder;
vector <int> components[200005];
int component[200005], sizes[200005];
bool visitedOrder[200005], visitedComponents[200005];
// Build an order of node such that IF there is a path from X to Y, then Y will be before X in the order
// This order is later on reversed so that X will be before Y
void buildOrder(int node) {
visitedOrder[node] = true;
for (auto x : graph[node]) {
if (visitedOrder[x]) continue;
buildOrder(x);
}
depOrder.emplace_back(node);
}
// Build the components based on the order that was generated. We know from the order that if I can only reach
// from X to Y (and not from Y to X), X will be computed first. Therefore, by the time we compute Y, X will already be
// visited. If we reach Y coming from X on the reversed graph, that means that X is reachable from Y on the initial graph.
// Moreover, if Y is not already visited, it means that Y is after X in the order of nodes, so Y must also be reachable
// from X on the initial graph. Therefore, X and Y are in the same strongly connected component.
void buildComponents(int node, int currentComponent) {
visitedComponents[node] = true;
for (auto x : revGraph[node]) {
if (visitedComponents[x]) continue;
buildComponents(x, currentComponent);
}
components[currentComponent].emplace_back(node);
sizes[currentComponent] += 1;
component[node] = currentComponent;
}
set <int> componentsGraph[200005];
vector <pair <int, int>> edges;
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
edges.emplace_back(x, y);
graph[x].emplace_back(y);
revGraph[y].emplace_back(x);
}
for (int i = 1; i <= n; ++i) {
if (visitedOrder[i]) continue;
buildOrder(i);
}
reverse(depOrder.begin(), depOrder.end());
int nComponents = 0;
for (auto node : depOrder) {
if (visitedComponents[node]) continue;
nComponents += 1;
buildComponents(node, nComponents);
}
for (auto edge : edges) {
if (component[edge.first] == component[edge.second]) continue;
componentsGraph[component[edge.first]].insert(component[edge.second]);
}
cout << nComponents << '\n';
for (int i = 1; i <= nComponents; ++i) {
for (auto node : components[i]) {
cout << node << ' ';
}
cout << '\n';
}
return 0;
}