Pagini recente » Cod sursa (job #1185897) | Cod sursa (job #79817) | Cod sursa (job #1190882) | Cod sursa (job #1546426) | Cod sursa (job #1787981)
#include <bits/stdc++.h>
using namespace std;
using vit = vector<int>::reverse_iterator;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
int n, m, d[NMAX], ctcs;
vector<int> v[NMAX];
vector<int> ctc[NMAX];
bool inStack[NMAX];
stack<int> stk;
int tarjan(int node, int depth) {
d[node] = depth;
stk.push(node);
inStack[node] = 1;
for (const int& x: v[node]) {
if (d[x] == 0) {
d[node] = min(d[node], tarjan(x, depth + 1));
}
else if (inStack[x]) {
d[node] = min(d[node], d[x]);
}
}
if (d[node] == depth) {
++ctcs;
int x;
do {
x = stk.top();
stk.pop();
inStack[x] = false;
ctc[ctcs].push_back(x);
} while (x != node);
}
return d[node];
}
int main()
{
fin >> n >> m;
for (int x, y; m; --m) {
fin >> x >> y;
v[x].push_back(y);
}
int x;
for (int i = 1; i <= n; ++i) {
if (!d[i]) {
x = tarjan(i, 1);
}
}
fout << ctcs << '\n';
for (int i = 1; i <= ctcs; ++i) {
for (const int& x: ctc[i])
fout << x << ' ';
fout << '\n';
}
return 0;
}