Pagini recente » Cod sursa (job #2186587) | Cod sursa (job #1057116) | Cod sursa (job #2948725) | Cod sursa (job #2219020) | Cod sursa (job #1423693)
#include<cstdio>
const int nrMaxNoduri = 100000,
nrMaxMuchii = 200000;
int st[nrMaxNoduri], vf, val[nrMaxMuchii], urm[nrMaxMuchii], lst[nrMaxNoduri], sol[nrMaxNoduri],cnt,nrc;
int index[nrMaxNoduri], n, m, nrd, ind, low_level[nrMaxNoduri];
bool viz[nrMaxNoduri];
int minim (int a, int b){
return a<b?a:b;
}
void dfs (int node){
int pozc = vf;
viz[node] = 1;
low_level[node] = index[node] = ++ind;
st[vf++] = node;
int pozv = lst[node], vec;
while(pozv != -1){
vec = val[pozv];
if(!viz[vec]){
dfs(vec);
low_level[node] = minim(low_level[node], low_level[vec]);
}else{
low_level[node] = minim(low_level[node], low_level[vec]);
}
pozv = urm[pozv];
}
if(index[node] == low_level[node]){
//Putem considera nodul ca fiind radacina componentei tare conexe
++nrc;
sol[cnt++] = vf - pozc;
int nd;
do{
nd = st[--vf];
sol[cnt++] = nd;
}while(nd != node);
}
}
int main (){
FILE *in = fopen("ctc.in","r");
FILE *out = fopen("ctc.out","w");
fscanf(in,"%d%d",&n,&m);
for(int i = 0 ; i < n ; i++) lst[i] = -1;
int x, y;
for(int i = 0 ; i < m ; i++){
fscanf(in,"%d%d",&x,&y);
y--;x--;
val[i] = y;
urm[i] = lst[x];
lst[x] = i;
}
for(int i = 0 ; i < n && nrd < n ; i++){
if(!viz[i])
dfs(i);
}
fprintf(out,"%d\n",nrc);
for(int i = 0 , j = 0 ; i < cnt ; i++){
if(j == 0){
j = sol[i];
}else{
j--;
fprintf(out,"%d ",sol[i] + 1);
}
if(j == 0){
fprintf(out,"\n");
}
}
return 0;
}