Pagini recente » Cod sursa (job #1500746) | Cod sursa (job #2202569) | Cod sursa (job #2272279) | Cod sursa (job #75041) | Cod sursa (job #2277405)
#include <cstdio>
#include <set>
#include <stack>
#include <vector>
const int MAX_N = 1e5;
int lowlink[2 + MAX_N], index[2 + MAX_N], count, global;
bool inStack[2 + MAX_N];
std::vector<int> neighbours[2 + MAX_N];
std::set<int> sol[2 + MAX_N];
std::stack<int> nodes;
void connect(int u) {
index[u] = count;
lowlink[u] = count;
inStack[u] = true;
count++;
nodes.push(u);
for (int v : neighbours[u])
if (index[v] == 0) {
connect(v);
lowlink[u] = std::min(lowlink[u], lowlink[v]);
} else if (inStack[v])
lowlink[u] = std::min(lowlink[u], index[v]);
if (lowlink[u] == index[u]) {
global++;
int v;
do {
v = nodes.top();
inStack[v] = false;
sol[global].insert(v);
nodes.pop();
} while (v != u);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
neighbours[u].push_back(v);
}
for (int u = 1; u <= n; u++)
if (index[u] == 0)
connect(u);
printf("%d\n", global);
for (int i = 1; i <= global; i++) {
for (int j : sol[i])
printf("%d ", j);
printf("\n");
}
return 0;
}