Pagini recente » Cod sursa (job #1059730) | Cod sursa (job #106902) | Cod sursa (job #3033297) | Cod sursa (job #269624) | Cod sursa (job #1787982)
#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, idx[NMAX], lowlink[NMAX], ctcs, index;
vector<int> v[NMAX];
vector<int> ctc[NMAX];
bool inStack[NMAX];
stack<int> stk;
void tarjan(int node) {
++index;
idx[node] = index;
lowlink[node] = index;
stk.push(node);
inStack[node] = 1;
for (const int& x: v[node]) {
if (!idx[x]) {
tarjan(x);
lowlink[node] = min(lowlink[node], lowlink[x]);
}
else if (inStack[x]) {
lowlink[node] = min(lowlink[node], lowlink[x]);
}
}
if (idx[node] == lowlink[node]) {
int x;
++ctcs;
do {
x = stk.top();
stk.pop();
inStack[x] = 0;
ctc[ctcs].push_back(x);
} while (x != node);
}
}
int main()
{
fin >> n >> m;
for (int x, y; m; --m) {
fin >> x >> y;
v[x].push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!idx[i]) {
tarjan(i);
}
}
fout << ctcs << '\n';
for (int i = 1; i <= ctcs; ++i) {
for (const int& x: ctc[i])
fout << x << ' ';
fout << '\n';
}
return 0;
}