Pagini recente » Cod sursa (job #1159783) | Cod sursa (job #1234692) | Cod sursa (job #308558) | Cod sursa (job #2565938) | Cod sursa (job #2401429)
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 10000
#define MAXM 20000
#define vi vector<int>
#define vvi vector<vi>
#define pb(x) push_back(x)
#define pp() pop_back()
using namespace std;
int ut[MAXN], nd[2 * MAXM], nxt[2 * MAXM], dr;
int dep[MAXN], dth = 1, mndth;
vvi comp;
int dc;
vi s;
void add(int x, int y){
nd[dr] = y;
nxt[dr] = ut[x];
ut[x] = dr;
dr++;
}
void group(int x){
s.pb(x);
int p = ut[x], md = dth;
dep[x] = dth++;
while(p != -1){
if(dep[nd[p]] == 0){
group(nd[p]);
if(dep[nd[p]] < dep[x])
dep[x] = dep[nd[p]];
}
else if(dep[nd[p]] >= mndth){
if(dep[nd[p]] < dep[x])
dep[x] = dep[nd[p]];
}
p = nxt[p];
}
if(dep[x] == md){
vi aux;
do{
aux.pb(s.back());
s.pp();
}while(aux.back() != x);
comp.pb(aux);
dc++;
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, i, x, y;
scanf("%d%d", &n, &m);
memset(ut, -1, sizeof ut);
for(i = 0; i < m; i++){
scanf("%d%d", &x, &y);
x--;
y--;
add(x, y);
}
for(i = 0; i < n; i++){
if(dep[i] == 0){
mndth = dth;
group(i);
}
}
printf("%d\n", comp.size());
for(auto &it : comp){
for(auto &it2 : it){
printf("%d ", it2 + 1);
}
fputc('\n', stdout);
}
return 0;
}