Pagini recente » Cod sursa (job #1793208) | Cod sursa (job #2413753) | Cod sursa (job #2052919) | Cod sursa (job #2156183) | Cod sursa (job #956888)
Cod sursa(job #956888)
#include<fstream>
#include<vector>
#include<list>
using namespace std;
vector< bool > v;
vector< list<int> > edges;
void dfs(int s){
int x;
list<int> q;
q.push_back(s);
while(q.size()){
x = q.front(), q.pop_front();
for(auto it=edges[x].begin(); it!=edges[x].end(); it++){
if(!v[*it]) v[*it]=true, q.push_back(*it);
}
}
}
int main(){
int count=0, n, m, x, y, i;
freopen("dfs.in", "rt", stdin);
freopen("dfs.out", "wt", stdout);
scanf("%d %d", &n, &m);
edges.resize(n+1), v.resize(n+1, false);
for(i=0; i<m ;i++){
scanf("%d %d", &x, &y);
edges[x].push_back(y);
edges[y].push_back(x);
}
for(i=1; i<=n; i++)
if(!v[i]) dfs(i), count++;
printf("%d\n", count);
fclose(stdin);
fclose(stdout);
return 0;
}