Pagini recente » Cod sursa (job #1634991) | Cod sursa (job #1014729) | Cod sursa (job #2527726) | Cod sursa (job #2972370) | Cod sursa (job #700225)
Cod sursa(job #700225)
#include<stdio.h>
#include<cstring>
using namespace std;
int n,m,k;
int viza[100002],vizb[100002];
struct nod
{
int v;
nod *adresa;
};
nod *a[100002],*b[100002];
void add(int x,int y)
{
nod *p;
p=new nod;
p->v=y;
p->adresa=a[x];
a[x]=p;
p=new nod;
p->v=x;
p->adresa=b[y];
b[y]=p;
}
void citire()
{
int i,x,y;
scanf("%d %d",&n,&m);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
add(x,y);
}
fclose(stdin);
}
void dfa(int x)
{
nod *p;
viza[x]=k;
for(p=a[x];p;p=p->adresa)
if(viza[p->v]==0)
dfa(p->v);
}
void dfb(int x)
{
nod *p;
vizb[x]=k;
for(p=b[x];p;p=p->adresa)
if(vizb[p->v]==0)
dfb(p->v);
}
void scrie()
{
int i,j;
printf("%d\n",k);
for(i=1;i<=k;i++)
{
for(j=1;j<=n;j++)
if(viza[j]==i)
printf("%d ",j);
printf("\n");
}
fclose(stdout);
}
int vmin(int x,int y)
{
return(x<y)?x:y;
}
int main()
{
int i,j,q;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
k=0;
for(i=1;i<=n;i++)
if(viza[i]==0 && vizb[i]==0)
{
++k;
dfa(i);
dfb(i);
for(j=1;j<=n;j++)
{
q=vmin(viza[j],vizb[j]);
viza[j]=q;
vizb[j]=q;
}
}
scrie();
return 0;
}