Pagini recente » Cod sursa (job #882984) | Cod sursa (job #3220723) | Cod sursa (job #2038035) | Cod sursa (job #3152193) | Cod sursa (job #2681939)
#include <fstream>
#include <vector>
using namespace std;
void DFS(int currentNode, vector<vector<int>>& arches, vector<int>& visited) {
if (visited[currentNode] == 1)
return;
visited[currentNode] = 1;
int length = arches[currentNode].size();
for (int i = 1; i < length; ++i) {
DFS(arches[currentNode][i] - 1, arches, visited);
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
fin >> N >> M;
vector<vector<int>> arches(N, vector<int>(1, -1));
vector<int> visited(N, 0);
int x, y;
for (int i = 0; i < M; ++i) {
fin >> x >> y;
arches[x - 1].push_back(y);
arches[y - 1].push_back(x);
}
int numberComponents = 0;
for (int i = 0; i < N; ++i) {
if (visited[i] == 0) {
DFS(i, arches, visited);
++numberComponents;
}
}
fout << numberComponents;
return 0;
}