Pagini recente » Cod sursa (job #2593387) | Cod sursa (job #1674698) | Cod sursa (job #1436479) | Cod sursa (job #1544755) | Cod sursa (job #1580965)
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,i,x,y,nr,viz[NMAX];
struct nod{
int inf;
nod *urm;}*p,*v[NMAX];
void afis(nod *p)
{
nod *u;
u=p;
while(u!=NULL)
{
g<<u->inf<<" ";
u=u->urm;
}
g<<endl;
}
void adaug(nod *&p,int x)
{
nod *u,*q;
q=new nod;
q->inf=x;
q->urm=NULL;
u=p;
if(p==NULL) p=q;
else
{
while(u->urm!=NULL)
u=u->urm;
u->urm=q;
}
}
void BF(int X)
{
int C[NMAX],p,u,k;
nod *q;
p=1;
u=1;
C[p]=X;
viz[X]=1;
while(p<=u)
{
k=C[p];
q=v[k];
while(q!=NULL)
{
if(viz[q->inf]==0)
{
C[++u]=q->inf;
viz[q->inf]=1;
}
q=q->urm;
}
p++;
}
}
int main()
{
f>>n>>m;
for(i=1;i<=n;i++)
v[i]=NULL;
for(i=1;i<=m;i++)
{
f>>x>>y;
adaug(v[x],y);
adaug(v[y],x);
}
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
BF(i);
nr++;
}
}
g<<nr<<endl;
return 0;
}