Pagini recente » Cod sursa (job #1081882) | Cod sursa (job #907602) | Cod sursa (job #2101809) | Cod sursa (job #3133831) | Cod sursa (job #2858103)
#include <stdio.h>
#include <vector>
using namespace std;
#define MAX_N 100000
struct Node{
int subset;
vector<int> edges;
};
Node nodes[MAX_N];
void add(int a,int b){
nodes[a].edges.push_back(b);
nodes[b].edges.push_back(a);
}
void dfs(int nodeIndex,int subset){
nodes[nodeIndex].subset=subset;
for(int n : nodes[nodeIndex].edges)
if(nodes[n].subset!=subset)
dfs(n,subset);
}
int main(){
FILE *fin,*fout;
fin=fopen("dfs.in","r");
fout=fopen("dfs.out","w");
int n,m,i,a,b,nr;
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&a,&b);
add(a,b);
}
nr=0;
for(i=1;i<=n;i++)
if(nodes[i].subset==0)
dfs(i,++nr);
fprintf(fout,"%d",nr);
fclose(fin);
fclose(fout);
return 0;
}