Cod sursa(job #3287019)
Utilizator | Data | 14 martie 2025 22:43:39 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.7 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector<int> a[100001];
int d[100001] = {0};
void dfs(int x)
{
d[x] = 1;
int k = a[x].size();
for(int i = 0; i < k; i++)
{
if(d[a[x][i]] == 0)
{
dfs(a[x][i]);
}
}
}
int main()
{
int N, M;
in >> N >> M;
for(int i = 1; i <= M; i++)
{
int x, y;
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
int c = 0;
for(int i = 1; i <= N; i++)
{
if(d[i] == 0)
{
dfs(i);
c ++;
}
}
out << c;
return 0;
}