Pagini recente » Cod sursa (job #606895) | Cod sursa (job #2788915) | Cod sursa (job #360657) | Cod sursa (job #1321307) | Cod sursa (job #256981)
Cod sursa(job #256981)
#include <iostream.h>
#include <fstream.h>
#define IN "dfs.in"
#define OUT "dfs.out"
#define maxx 100002
ifstream fin(IN);
ofstream fout(OUT);
int n,m;
struct lista
{
int nod;
lista *urm;
}*g[maxx];
int u[maxx];
void citire();
void add(int x,int y);
void df(int nod);
void comp_con();
void afis()
{
int i;
lista *q;
for(i=1;i<=n;i++)
{
q=g[i];
fout<<i<<" ";
while(q)
{
fout<<q->nod<<" ";
q=q->urm;
}
fout<<endl;
}
}
int main()
{
citire();
fin.close();
comp_con();
fout<<endl;
//afis();
fout.close();
return 0;
}
void citire()
{
int i;
int x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x;
fin>>y;
add(x,y);
add(y,x);
}
}
void add(int x,int y)
{
lista *q;
q=new lista;
q->nod=y;
q->urm=g[x];
g[x]=q;
}
void df(int nod)
{
lista *p;
u[nod]=1;
for(p=g[nod];p!=NULL;p=p->urm)
if(!u[p->nod])
df(p->nod);
}
void comp_con()
{
int i;
int v=0;
memset(u,0,sizeof(u));
for(i=1;i<=n;i++)
if(!u[i])
{
df(i);
v++;
}
fout<<v;
}