Pagini recente » Cod sursa (job #3264229) | Cod sursa (job #3187666) | Cod sursa (job #2329203) | Cod sursa (job #30017) | Cod sursa (job #1426457)
#include <fstream>
#include <vector>
#define MaxN 100005
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M, conexes, color[MaxN];
vector<int> neighbours[MaxN];
void dfs(int v) {
color[v] = GRAY;
for (int i = 0; i < neighbours[v].size(); ++i) {
int u = neighbours[v][i];
if (color[u] == WHITE) {
dfs(u);
}
}
color[v] = BLACK;
}
int main() {
fin >> N >> M;
for (int i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
neighbours[x].push_back(y);
neighbours[y].push_back(x);
}
for (int i = 1; i <= N; ++i) {
if (color[i] == WHITE) {
++conexes;
dfs(i);
}
}
fout << conexes << '\n';
return 0;
}