Pagini recente » Cod sursa (job #1568229) | Cod sursa (job #2736186) | Cod sursa (job #1297492) | Cod sursa (job #866628) | Cod sursa (job #1904562)
#include <bits/stdc++.h>
#define NMAX 100005
#define min(a, b) ( (a > b) ? b : a)
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector < int > a[NMAX], aux, idx(NMAX), lowlink(NMAX);
bitset < NMAX > in_stack;
vector < vector < int > > sol;
stack < int > stk;
int n, m, x, y, ind;
void tarjan(int nod) {
ind++;
idx[nod] = lowlink[nod] = ind;
stk.push(nod);
in_stack[nod] = 1;
for (unsigned i = 0; i < a[nod].size(); i++) {
int next = a[nod][i];
if (!idx[next]) {
tarjan(next);
lowlink[nod] = min(lowlink[nod], lowlink[next]);
} else if (in_stack[next])
lowlink[nod] = min(lowlink[nod], lowlink[next]);
}
if (idx[nod] == lowlink[nod]) {
int x;
aux.clear();
do {
x = stk.top();
in_stack[x] = 0;
stk.pop();
aux.push_back(x);
} while (x != nod);
sol.push_back(aux);
}
}
int main() {
f>>n>>m;
while (m--) {
f>>x>>y;
a[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (!idx[i]) tarjan(i);
g<<sol.size()<<'\n';
for (unsigned i = 0; i < sol.size(); i++) {
for (unsigned j = 0; j < sol[i].size(); j++)
g<<sol[i][j]<<' ';
g<<'\n';
}
return 0;
}