Pagini recente » Cod sursa (job #1066664) | Cod sursa (job #1005025) | Cod sursa (job #1465628) | Cod sursa (job #1100318) | Cod sursa (job #720614)
Cod sursa(job #720614)
#include<stdio.h>
#include<assert.h>
#include<vector>
#include<algorithm>
using namespace std;
const int knmax = 100005;
int verts, edges, sol, vis[knmax];
vector<int> graph[knmax];
void read(){
assert(freopen("dfs.in", "r", stdin) != NULL);
scanf("%d%d", &verts, &edges);
int i, aux_x, aux_y;
for(i = 1; i <= edges; ++i){
scanf("%d%d", &aux_x, &aux_y);
graph[aux_x].push_back(aux_y);
graph[aux_y].push_back(aux_x);
}
}
void dfs(int x){
vis[x] = 1;
vector<int>::iterator it;
for(it = graph[x].begin(); it < graph[x].end(); ++it)
if(!vis[*it])
dfs(*it);
}
void solve(){
for(int i = 1; i <= verts; ++i)
if(!vis[i]){
dfs(i);
++sol;
}
}
void write(){
assert(freopen("dfs.out", "w", stdout) != NULL);
printf("%d", sol);
}
int main(){
read();
solve();
write();
return 0;
}