Pagini recente » Cod sursa (job #2710898) | Cod sursa (job #1519285) | Cod sursa (job #133140) | Cod sursa (job #2712877) | Cod sursa (job #2401443)
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 100000
#define MAXM 200000
#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[MAXM], nxt[MAXM], dr;
int dep[MAXN], dth = 1;
char pus[MAXN];
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){
if(x == 485){
x++;
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(!pus[nd[p]]){
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());
pus[s.back()] = 1;
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(!pus[i]){
group(i);
}
}
printf("%d\n", comp.size());
for(auto &it : comp){
for(auto &it2 : it){
printf("%d ", it2 + 1);
}
fputc('\n', stdout);
}
return 0;
}