Pagini recente » Cod sursa (job #558681) | Cod sursa (job #371991) | Cod sursa (job #3127498) | Cod sursa (job #3261959) | Cod sursa (job #1203801)
#include <cstdio>
using namespace std;
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
int n,m,compon;
int v[2][1000005],prim[100001];
int p[100001],c[500000],nrc,mu;
inline void creeaza(int x,int y,int i)
{v[0][i]=y;
v[1][i]=prim[x];
prim[x]=i;
}
int main()
{int i,j,s,x,y,k;
fscanf(f,"%d %d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f,"%d %d",&x,&y);
creeaza(x,y,++mu);
creeaza(y,x,++mu);
}
for (k=1;k<=n;k++) if (p[k]==0)
{p[k]=++compon;
nrc=1;
c[nrc]=k;
i=1;
while (i<=nrc) {j=prim[c[i]];
while (j!=0) {if (p[v[0][j]]==0) {p[v[0][j]]=compon;
c[++nrc]=v[0][j];
}
j=v[1][j];
}
i++;
}
}
fprintf(g,"%d\n",compon);
return 0;
}