Pagini recente » Cod sursa (job #1863446) | Cod sursa (job #2824052) | Cod sursa (job #1694127) | Cod sursa (job #1597421) | Cod sursa (job #314192)
Cod sursa(job #314192)
#include<stdio.h>
#define NMAX 100003
struct lista {
int x;
lista *next;
};
int n,m,i,id=0,nc=0,index[NMAX],lowlink[NMAX],is[NMAX];
lista* v[NMAX];
lista *comp[NMAX];
lista *s=NULL,*q;
void push(lista* &lst,int nod) {
lista *q=new lista;
q->x=nod;
q->next=lst;
lst=q;
}
int pop(lista* &lst) {
lista *q=lst;
lst=lst->next;
int rez=q->x;
delete q;
return rez;
}
void citeste() {
int i,x,y;
freopen("ctc.in","r",stdin);
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
v[i]=NULL;
is[i]=0;
index[i]=-1;
}
for(i=0;i<m;i++) {
scanf("%d %d",&x,&y);
push(v[x],y);
}
fclose(stdin);
}
void tarjan(int nod) {
int nd;
index[nod]=lowlink[nod]=id;
id++;
push(s,nod);
is[nod]=1;
lista *q=v[nod];
while(q) {
if(index[q->x]==-1) {
tarjan(q->x);
if(lowlink[q->x]<lowlink[nod]) lowlink[nod]=lowlink[q->x];
}
else
if(is[q->x])
if(index[q->x]<lowlink[nod]) lowlink[nod]=index[q->x];
q=q->next;
}
if(lowlink[nod]==index[nod]) {
comp[nc]=NULL;
do {
nd=pop(s);
push(comp[nc],nd);
} while (nod!=nd);
++nc;
}
}
int main() {
citeste();
for(i=1;i<=n;i++)
if(index[i]==-1) tarjan(i);
freopen("ctc.out","w",stdout);
printf("%d\n",nc);
for(i=0;i<nc;i++) {
while(comp[i]) printf("%d ",pop(comp[i]));
printf("\n");
}
fclose(stdout);
return 0;
}