Pagini recente » Cod sursa (job #2588973) | Cod sursa (job #429781) | Cod sursa (job #2808880) | Cod sursa (job #245835) | Cod sursa (job #3335598)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N = 1e5;
vector<int> lista_ad[N + 1];
bool vizitat[N + 1];
int nr_cc = 1;
void adancime(int plecare)
{
for (int v : lista_ad[plecare])
{
// parcurgem vecinii nevizitati - in adancime
if (!vizitat[v])
{
vizitat[v] = true;
adancime(v);
}
}
}
void dfs(int n, int m)
{
for (int i = 1; i <= n; i++)
vizitat[i] = false;
vizitat[1] = true;
adancime(1);
for (int i = 1; i <= n; i++)
{
if (!vizitat[i])
{
// mai exista noduri nevizitate deci avem cel putin 2 cc
nr_cc++;
adancime(i);
}
}
}
int main()
{
int n, m;
in >> n >> m;
int u, v;
for (int i = 0; i < m; i++)
{
in >> u >> v;
lista_ad[u].push_back(v);
lista_ad[v].push_back(u);
}
dfs(n, m);
out << nr_cc;
return 0;
}