Pagini recente » Cod sursa (job #2782661) | Cod sursa (job #3280988) | Cod sursa (job #1382370) | Cod sursa (job #1478771) | Cod sursa (job #516927)
Cod sursa(job #516927)
#include<stdio.h>
#include<stdlib.h>
#define N 100001
typedef struct nod
{long info;
struct nod *leg;}Nod,*list_ad;
typedef struct
{long grin;
list_ad lad;}head;
typedef head graf[N];
graf g;
typedef struct stack
{long st[N],sp;};
long n,m,c[N],i,j,k,t;
void add(list_ad &l,long x)
{Nod *px=new Nod;
px->info=x;
px->leg=l;
l=px;}
long del(list_ad &l)
{long x=l->info;
Nod *t=l->leg;
free(l);
l=t;
return x;}
void push(stack &s,long x)
{s.st[++s.sp]=x;}
long pop(stack &s)
{return s.st[s.sp--];}
int main()
{freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
stack s;
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
{c[i]=0;
g[i].grin=0;
g[i].lad=NULL;}
for(k=1;k<=m;k++)
{scanf("%ld%ld",&i,&j);
g[i].grin++;
g[j].grin++;
add(g[i].lad,j);
add(g[j].lad,i);}
t=0;
for(i=1;i<=n;i++)
if(c[i]==0)
{t++;
s.sp=0;
push(s,i);
while(s.sp!=0)
{k=pop(s);
c[k]=1;
while(g[k].grin!=0)
{j=del(g[k].lad);
g[k].grin--;
if(c[j]==0)
push(s,j);}}}
printf("%ld\n",t);
fclose(stdin);
fclose(stdout);
return 0;}