Pagini recente » Cod sursa (job #215252) | Cod sursa (job #1902017) | Cod sursa (job #1192254) | Cod sursa (job #1317782) | Cod sursa (job #1953542)
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <algorithm>
#include <vector>
using namespace std;
FILE *fin = fopen("ctc.in", "r");
FILE *fout = fopen("ctc.out", "w");
#define BUF 1 << 17
char buf[BUF];
int pos = BUF;
inline char next() {
if(pos == BUF)
fread(buf, 1, BUF, fin), pos = 0;
return buf[pos++];
}
inline int read() {
int x = 0;
char ch = next();
while(!isdigit(ch))
ch = next();
while(isdigit(ch))
x = x * 10 + ch - '0', ch = next();
return x;
}
#define MAX_N 100000
#define MAX_M 200000
int n, m;
vector <int> v[MAX_N + 1];
vector <int> sol[MAX_N + 1];
vector <int> stk;
int idx[MAX_N + 1];
int freeidx = 0;
bool ostk[MAX_N + 1];
int numCTC = 0;
int tarjan(int nod) {
int minPtr = idx[nod] = ++freeidx;
stk.push_back(nod);
ostk[nod] = 1;
for(auto &son : v[nod])
if(!idx[son])
minPtr = min(minPtr, tarjan(son));
else if(ostk[son])
minPtr = min(minPtr, idx[son]);
if(idx[nod] == minPtr) {
int aux;
do {
aux = stk[stk.size() - 1];
ostk[aux] = 0;
stk.pop_back();
sol[numCTC].push_back(aux);
} while(aux != nod);
numCTC++;
}
return minPtr;
}
int main() {
int i, x, y;
n = read(), m = read();
for(i = 1;i <= m;i++) {
x = read(), y = read();
v[x].push_back(y);
}
for(i = 1;i <= n;i++)
if(!idx[i])
tarjan(i);
fprintf(fout, "%d\n", numCTC);
for(i = 0;i < numCTC;i++) {
for(auto &nod: sol[i])
fprintf(fout, "%d ", nod);
fputc('\n', fout);
}
fclose(fin);
fclose(fout);
return 0;
}