Pagini recente » Cod sursa (job #159263) | Cod sursa (job #2348892) | Cod sursa (job #683853) | Cod sursa (job #933897) | Cod sursa (job #513834)
Cod sursa(job #513834)
#include<stdio.h>
#include<vector>
using namespace std;
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");
int M,i,N,K,x,y;
char Viz[100005];
vector<int>W[100005];
void dfs (int nod){
Viz[nod] = 1;
int C[100005];
int p = 1; int u = 1;
C[1] = nod;
vector<int>::iterator itt;
while ( p <= u ) {
for ( itt = W[C[p]].begin() ; itt != W[C[p]].end() ; ++itt ){
if ( !Viz[ *itt ] ){
Viz[ *itt ] = 1;
C[++u] = *itt;
}
}
++p;
}
}
int main ( ) {
fscanf(f,"%d %d",&N,&M);
for ( i = 1 ; i <= M ; ++i ){
fscanf(f,"%d %d",&x,&y);
W[x].push_back(y);
W[y].push_back(x);
}
for ( i = 1 ; i <= N ; ++i ){
if ( !Viz[i] ){
++K;
dfs(i);
}
}
fprintf(g,"%d\n",K);
fclose(f);
fclose(g);
return 0;
}