Pagini recente » Arhiva de probleme | Cod sursa (job #348020) | Cod sursa (job #2849896) | Cod sursa (job #3211247) | Cod sursa (job #409729)
Cod sursa(job #409729)
#include<cstdio>
#include<fstream>
using namespace std;
struct nod{
int info;
nod *next;
};
nod *a[100005];
int n,m,nrc=0,v[100005];
void citire()
{
freopen("dfs.in","r",stdin);
scanf("%d%d", &n, &m);
int i,x,y;
nod *p;
for(i=1;i<=n;i++)
a[i]=NULL;
for(i=1;i<=m;i++)
{
scanf("%d%d", &x, &y);
p=new nod;
p->info=y;
p->next=a[x];
a[x]=p;
p=new nod;
p->info=x;
p->next=a[y];
a[y]=p;
}
}
void write()
{
int i;
for(i=1;i<=n;i++)
{
printf("%d: ",i);
for(nod *p=a[i];p;p=p->next)
printf("%d ", p->info);
printf("\n");
}
}
void dfs(int varf, int nrc)
{
v[varf]=nrc;
for(nod *p=a[varf];p;p=p->next)
if(v[p->info]==0)
dfs(p->info,nrc);
}
void bfs(int varf, int nrc)
{
int k;
nod *st,*dr;
st=dr=new nod;
st->info=varf;
st->next=NULL;
dr=st;
v[varf]=nrc;
while(st)
{
k=st->info;
for(nod *p=a[k];p;p=p->next)
{
if(v[p->info]==0)
{
v[p->info]=nrc;
nod *q=new nod;
q->info=p->info;
q->next=NULL;
dr->next=q;
dr=q;
}
}
nod *t=new nod;
t=st;
st=st->next;
delete t;
}
}
int main()
{
int i;
citire();
for(i=1;i<=n;i++)
if(v[i]==0)
bfs(i,++nrc);
freopen("dfs.out","w",stdout);
//write();
printf("%d",nrc);
return 0;
}