Pagini recente » Cod sursa (job #1463282) | Cod sursa (job #1463254) | Cod sursa (job #2941582) | Cod sursa (job #3291493) | Cod sursa (job #2193420)
#include <stdio.h>
#include <algorithm>
#include <vector>
const int MAX_N = 100000;
std::vector<int> neighbours[1 + MAX_N];
std::vector<int> neighboursT[1 + MAX_N];
bool visited[1 + MAX_N];
std::vector<int> dfsOrder;
int sccCount;
std::vector<int> sccs[MAX_N];
void dfs(int u) {
visited[u] = true;
for (int v : neighbours[u])
if (!visited[v])
dfs(v);
dfsOrder.push_back(u);
}
void dfsT(int u, int label) {
visited[u] = true;
sccs[label].push_back(u);
for (int v : neighboursT[u])
if (!visited[v])
dfsT(v, label);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
neighbours[u].push_back(v);
neighboursT[v].push_back(u);
}
for (int u = 1; u <= n; u++)
visited[u] = false;
for (int u = 1; u <= n; u++)
if (!visited[u])
dfs(u);
std::reverse(dfsOrder.begin(), dfsOrder.end());
for (int u = 1; u <= n; u++)
visited[u] = false;
sccCount = 0;
for (int u : dfsOrder)
if (!visited[u]) {
dfsT(u, sccCount);
sccCount++;
}
printf("%d\n", sccCount);
for (int i = 0; i < sccCount; i++) {
for (int u : sccs[i])
printf("%d ", u);
printf("\n");
}
return 0;
}