Pagini recente » Cod sursa (job #1353364) | Rating Lazar Mihai (MihaiLazar26) | Cod sursa (job #931153) | Cod sursa (job #291898) | Cod sursa (job #274331)
Cod sursa(job #274331)
#include<fstream.h>
ifstream f("dfs.in");
ofstream g("dfs.out");
#define Nmax 100100
long n,m,nr,viz[Nmax];
struct lista
{
long inf;
lista *urm;
}*a[Nmax];
void add(long x,long y)
{
lista * q=new lista;
q->inf=y;
q->urm=a[x];
a[x]=q;
}
void citire()
{
long x,y;
f>>n>>m;
for(long i=1;i<=m;i++)
{
f>>x>>y;
add(x,y);
add(y,x);
}
}
void dfs(int x)
{
lista *c=new lista;
c->inf=x;
c->urm=NULL;
lista *u=c;
while(c)
{
for(lista *q=a[c->inf];q;q=q->urm)
{
if(viz[q->inf]==0)
{
lista *p=new lista;
p->inf=q->inf;
p->urm=NULL;
u->urm=p;
u=p;
viz[q->inf]=1;
}
}
c=c->urm;
}
}
int main()
{
citire();
for(long i=1;i<=n;i++)
if(viz[i]==0)
{
dfs(i);
nr++;
}
g<<nr<<'\n';
f.close();
g.close();
return 0;
}