Pagini recente » Cod sursa (job #2488946) | Cod sursa (job #1942843) | Cod sursa (job #447427) | Cod sursa (job #1522766) | Cod sursa (job #1832318)
#include <cstdio>
#include <vector>
using namespace std;
vector <int> l[100001];
int c[100001],f[100001];
void bfs (int i){
int p,u,j;
p=u=1;
c[p]=i;
f[c[p]]=1;
while (p<=u){
for (j=0;j<l[c[p]].size();j++){
if (f[l[c[p]][j]]==0){
f[l[c[p]][j]]=1;
c[++u]=l[c[p]][j];
}
}
p++;
}
}
int main()
{
FILE *fin=fopen ("dfs.in","r");
FILE *fout=fopen ("dfs.out","w");
int n,m,a,b,conex,i;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&a,&b);
l[a].push_back(b);
l[b].push_back(a);
}
conex=0;
for (i=1;i<=n;i++){
if (f[i]==0){
conex++;
bfs(i);
}
}
fprintf (fout,"%d",conex);
return 0;
}