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