Pagini recente » Cod sursa (job #2903937) | Cod sursa (job #2267706) | Cod sursa (job #440831) | Cod sursa (job #1012117) | Cod sursa (job #953957)
Cod sursa(job #953957)
/*
* Algoritm pentru a determina numarul componentelor conexe ale unui graf
* neorientat.
*
* Idee: DFS
*/
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void dfs (int v, const vector <vector <int>> &G, vector <bool> &seen)
{
seen[v] = true;
for (size_t i = 0; i < G[v].size(); ++i)
if (!seen[G[v][i]])
{
dfs (G[v][i], G, seen);
}
}
int main()
{
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n, m;
fin >> n >> m;
vector <vector <int>> G (n+1);
for (; m; --m)
{
int x, y;
fin >> x >> y;
G[x].push_back (y);
G[y].push_back (x);
}
int components (0);
vector <bool> seen (n+1, false);
for (int v = 1; v <= n; ++v)
if (!seen[v])
{
dfs (v, G, seen);
++components;
}
fout << components << endl;
fin.close();
fout.close();
return EXIT_SUCCESS;
}