Cod sursa(job #1930555)
| Utilizator | Data | 19 martie 2017 00:15:22 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
# include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5;
int n, m, i, nr, x, y;
bool ap[Nmax];
vector <int> G[Nmax];
void dfs(int x)
{
ap[x] = true;
for (auto &it: G[x])
if (!ap[it]) dfs(it);
}
int main ()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for (i = 1; i <= m; ++i)
{
scanf("%d %d\n", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
for (i = 1; i <= n; ++i)
{
if (!ap[i]) dfs(i), ++nr;
}
printf("%d\n", nr);
return 0;
}
