Pagini recente » Cod sursa (job #2944205) | Cod sursa (job #1467622) | Cod sursa (job #594241) | Cod sursa (job #2774143) | Cod sursa (job #1860370)
#include <bits/stdc++.h>
using namespace std;
//ifstream f("date.in");
//ofstream g("date.out");
struct Nod
{
int info;
Nod *next;
};
Nod *lista[100001], *listaT[100001];
unsigned int n, m, x, y, comp[100001], k, mat[10001][10001], nrLinii;
bool viz[100001], vizT[100001], used[100001];
void Adauga_in_Lista(Nod **p,int nod)
{
Nod *nou;
nou=(Nod*)malloc(sizeof(Nod));
nou->info=nod;
nou->next=*p;
*p=nou;
}
void DFS(int nod)
{
Nod *p;
viz[nod]=true;
for(p=lista[nod];p!=NULL;p=p->next)
if(!viz[p->info]) DFS(p->info);
}
void DFST(int nod)
{
Nod *p;
vizT[nod]=true;
for(p=listaT[nod];p!=NULL;p=p->next)
if(!vizT[p->info]) DFST(p->info);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
Adauga_in_Lista(&lista[x],y);
Adauga_in_Lista(&listaT[y],x);
}
for(int i=1;i<=n;i++)
{
if(!used[i])
{
for(int i=1;i<=n;i++) viz[i]=vizT[i]=false;
nrLinii++;
DFS(i);
DFST(i);
k=0;
for(int i=1;i<=n;i++)
{
if(viz[i] && vizT[i])
{
k++;
mat[nrLinii][k]=i;
used[i]=true;
}
}
mat[nrLinii][0]=k;
}
}
printf("%d\n",nrLinii);
for(int i=1;i<=nrLinii;i++)
{
for(int j=1;j<=mat[i][0];j++) printf("%d ",mat[i][j]);
printf("\n");
}
return 0;
}