Pagini recente » Cod sursa (job #2255613) | Cod sursa (job #950683) | Cod sursa (job #1759002) | Istoria paginii runda/oji_simu_2014 | Cod sursa (job #2496737)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void DFS(int i,vector<vector<int>>&graph,vector<bool>&visited) {
visited[i] = true;
for (int j = 0; j < graph[i].size(); j++)
if (!visited[graph[i][j]])
DFS(graph[i][j], graph,visited);
}
int main() {
int n, m;
int x, y;
fin >> n >> m;
int conex_components = 0;
vector<vector<int>>graph(n+1);
vector<bool>visited(n+1);
for (int i = 1; i <= n; i++)
visited[i] = false;
for (int i = 0; i < m; i++) {
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
conex_components++;
DFS(i, graph, visited);
}
}
fout << conex_components;
return 0;
}