Pagini recente » Cod sursa (job #2227885) | Cod sursa (job #2649431) | Cod sursa (job #1209967) | Cod sursa (job #782197) | Cod sursa (job #1034916)
#include <stdio.h>
using namespace std;
const int N=100001;
const int M=200001;
const int NIL=-1;
struct nod
{
int val;
int urm;
};
nod a[2*M];
int list[N],n,m,nr=0;
bool vizitat[N];
void marcheaza(int x)
{
int y,poz;
vizitat[x]=1;
poz=list[x];
while(poz!=NIL)
{
y=a[poz].val;
if(!vizitat[y]) marcheaza(y);
poz=a[poz].urm;
}
return;
}
int main()
{
FILE *in,*out;
in=fopen("dfs.in","r");
out=fopen("dfs.out","w");
int i,p,nc=0,x,y;
fscanf(in,"%d%d",&n,&m);
for(i=1;i<=n;i++) {list[i]=NIL; vizitat[i]=0;}
for(i=1;i<=m;i++)
{
fscanf(in,"%d%d",&x,&y);
a[nr].val=y;
a[nr].urm=list[x];
list[y]=nr++;
a[nr].val=x;
a[nr].urm=list[y];
list[x]=nr++;
}
p=1;
while(p<=n)
{
marcheaza(p);
while(p<=n && vizitat[p]) p++;
nc++;
}
fprintf(out,"%d",nc);
return 0;
}