Pagini recente » Cod sursa (job #2877385) | Cod sursa (job #2251776) | Cod sursa (job #1850966) | Cod sursa (job #240106) | Cod sursa (job #2265737)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct Item
{
long long val;
Item *next;
};
struct ListaAd
{
Item *st,*cur;
};
int n,m,a,b,i,iaux;
ListaAd Adiac[100005],AdiacT[100005];
bool Viz[100005];
int Mem[100005],Grupe[100005];
int nrmem,nrcomp,out;
Item *elem;
void dfs(int);
void dfs2(int);
int main()
{
fin>>n>>m;
for (i=1;i<=n;i++)
{
Adiac[i].st=new Item;
Adiac[i].st->val=0;
Adiac[i].cur=Adiac[i].st;
AdiacT[i].st=new Item;
AdiacT[i].st->val=0;
AdiacT[i].cur=AdiacT[i].st;
}
Viz[0]=1;
while (m!=0)
{
m--;
fin>>a>>b;
elem=new Item;
elem->val=b;
Adiac[a].cur->next=elem;
Adiac[a].cur=elem;
Adiac[a].cur->next=0;
elem=new Item;
elem->val=a;
AdiacT[b].cur->next=elem;
AdiacT[b].cur=elem;
AdiacT[b].cur->next=0;
}
for (i=1;i<=n;i++)
if (Viz[i]==0)
{
Viz[i]=1;
dfs(i);
nrmem++;
Mem[nrmem]=i;
}
for (i=1;i<=n;i++)
Adiac[i].st=AdiacT[i].st;
for (i=1;i<=n;i++)
Viz[i]=0;
while (nrmem!=0)
{
if (Viz[Mem[nrmem]]==0)
{
nrcomp++;
Grupe[Mem[nrmem]]=nrcomp;
Viz[Mem[nrmem]]=1;
dfs2(Mem[nrmem]);
}
nrmem--;
}
fout<<nrcomp<<"\n";
for (i=1;i<=nrcomp;i++)
{
for (iaux=1;iaux<=n;iaux++)
if (Grupe[iaux]==i)
fout<<iaux<<" ";
fout<<"\n";
}
return 0;
}
void dfs(int nod)
{
Item *caut;
int i2;
caut=Adiac[nod].st;
while (caut!=NULL)
{
i2=caut->val;
if (Viz[i2]==0)
{
Viz[i2]=1;
dfs(i2);
nrmem++;
Mem[nrmem]=i2;
}
caut=caut->next;
}
}
void dfs2(int nod)
{
Item *caut;
int i2;
caut=Adiac[nod].st;
while (caut!=NULL)
{
i2=caut->val;
if (Viz[i2]==0)
{
Grupe[i2]=nrcomp;
Viz[i2]=1;
dfs2(i2);
}
caut=caut->next;
}
}