Pagini recente » Cod sursa (job #1976854) | Cod sursa (job #964205) | Cod sursa (job #3196920) | Cod sursa (job #1841357) | Cod sursa (job #1106704)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#define NMax 100010
using namespace std;
const char IN[] = "ctc.in", OUT[] = "ctc.out";
int N, M;
vector<int> ad[NMax];
vector<vector<int> > Sol;
void tarjan( int x ) {
static int low[NMax], idx[NMax], index;
static bool b[NMax], inStack[NMax];
static stack<int> St;
static vector<int> vec;
int i;
if ( b[x] )
return ;
b[x] = true;
inStack[x] = true;
low[x] = idx[x] = ++ index;
St.push(x);
for ( i = 0; i < (int) ad[x].size(); ++ i) {
if ( ! b[ ad[x][i] ] ) {
tarjan( ad[x][i] );
low[x] = min( low[x], low[ad[x][i]]);
} else if ( inStack[ ad[x][i] ] )
low[x] = min( low[x], low[ad[x][i]]);
}
if ( low[x] == idx[x] ) { // muhahahah
vec.clear();
do {
i = St.top(); St.pop();
vec.push_back(i);
inStack[i] = false;
} while ( i != x );
Sol.push_back(vec);
}
}
int main() {
int i, j, x, y;
freopen(IN, "r", stdin);
scanf("%d%d", &N, &M);
for ( i = 1; i <= M; ++ i) {
scanf("%d %d", &x, &y);
ad[x].push_back(y);
}
fclose ( stdin );
for ( i = 1; i <= N; ++ i) tarjan( i );
freopen( OUT, "w", stdout);
printf("%d\n", (int) Sol.size() );
for ( i = 0; i < (int) Sol.size(); ++ i) {
sort( Sol[i].begin(), Sol[i].end() );
for ( j = 0; j < (int) Sol[i].size(); ++ j)
printf("%d ", Sol[i][j]);
printf("\n");
}
fclose(stdout);
return 0;
}