Pagini recente » Cod sursa (job #2893678) | Cod sursa (job #3212590) | Cod sursa (job #288171) | Cod sursa (job #3169688) | Cod sursa (job #326174)
Cod sursa(job #326174)
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAXN 100005
#define pb push_back
int N, M;
vector< int > G[MAXN], C;
vector< vector<int> > CTC;
stack< int > S;
int indecs[MAXN], lowlink[MAXN], inStack[MAXN];
int ind;
void read () {
int x, y;
for (scanf ("%d %d", &N, &M); M--; ){
scanf ("\n%d %d", &x, &y);
G[x].pb(y);
}
}
inline int min (int a, int b) {
return a < b ? a : b;
}
void tarjan (int nod) {
indecs[nod] = lowlink[nod] = ++ind;
S.push(nod);
inStack[nod] = 1;
int sz = G[nod].size();
for (int i = 0; i < sz; ++ i) {
if (!indecs[G[nod][i]]) {
tarjan (G[nod][i]);
lowlink[nod] = min (lowlink[G[nod][i]], lowlink[nod]);
}
else if (inStack[G[nod][i]])
lowlink[nod] = min (lowlink[G[nod][i]], lowlink[nod]);
}
if (lowlink[nod] == indecs[nod]) {
C.clear();
int n;
do {
n = S.top();
S.pop();
C.pb(n);
inStack[n] = 0;
}
while (nod != n);
CTC.pb(C);
}
}
void solve () {
for (int i = 1; i <= N; ++ i)
if (!indecs[i])
tarjan(i);
int sz = CTC.size();
printf ("%d\n", sz);
for (int i = 0; i < sz; ++ i){
int nrNodes = CTC[i].size();
for (int j = 0; j < nrNodes; ++ j) {
printf ("%d ", CTC[i][j]);
}
printf ("\n");
}
}
int main () {
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
read ();
solve ();
return 0;
}