Pagini recente » Cod sursa (job #1971644) | Cod sursa (job #2481156) | Cod sursa (job #2269819) | Cod sursa (job #1727345) | Cod sursa (job #2291464)
#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
const int MMAX = 200005;
int N, M;
vector<int> G[NMAX];
int low[NMAX];
int id[NMAX];
bool onStack[NMAX];
bool visited[NMAX];
stack<int> node_stack;
int id_count = 0;
vector<vector<int>> sol;
void dfs(int i) {
onStack[i] = true;
visited[i] = true;
id[i] = low[i] = id_count++;
node_stack.push(i);
for (auto node : G[i]) {
if (!visited[node]) {
dfs(node);
}
if (onStack[node]) {
low[i] = min(low[i], low[node]);
}
}
if (id[i] == low[i]) {
vector<int> ctc;
while (!node_stack.empty()) {
int top = node_stack.top();
low[top] = id[i];
ctc.push_back(top);
node_stack.pop();
onStack[top] = false;
if (top == i) {
break;
}
}
sol.push_back(ctc);
}
}
void tarjan() {
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
dfs(i);
}
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; ++i) {
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
}
tarjan();
printf("%d\n", int(sol.size()));
for (auto ctc : sol) {
for (auto node : ctc) {
printf("%d ", node);
}
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}