Pagini recente » Cod sursa (job #2941204) | Cod sursa (job #975565) | Cod sursa (job #23088) | Cod sursa (job #1985492) | Cod sursa (job #1451108)
#include <stdio.h>
#include <vector>
using namespace std;
int m, n, nodes = 0;
vector<int> visited;
vector< vector<int> > graph;
FILE *in = fopen ("dfs.in" , "r");
FILE *out = fopen ("dfs.out" , "w");
void dfs(int x) {
visited[x] = 1;
nodes++;
if(nodes == n)
return;
vector<int> list = graph.at(x);
for(vector<int>::const_iterator it = list.begin(); it != list.end(); it++) {
if(visited[*it] == 0)
dfs(*it);
}
}
int components() {
int comp = 0;
for(int i = 1; i <= n; i++) {
if(visited[i] == 0) {
comp++;
dfs(i);
}
}
return comp;
}
int main()
{
fscanf(in, "%d %d", &n, &m);
graph = vector< vector<int> >(n + 1, vector<int>());
visited = vector<int> (n+1, 0);
int x, y;
for(int i = 1; i <= m; i++) {
fscanf(in, "%d %d", &x, &y);
graph.at(x).push_back(y);
if(x != y)
graph.at(y).push_back(x);
}
/*int index = 0;
for(vector< vector<int> >::const_iterator it = graph.begin(); it != graph.end(); it++, index++) {
for(vector<int>::const_iterator jt = it->begin(); jt != it->end(); jt++) {
fprintf(out, "%d %d\n", index , *jt);
}
} */
int comp = components();
fprintf(out, "%d\n", comp);
fclose(in);
fclose(out);
return 0;
}