Pagini recente » Cod sursa (job #2665836) | Cod sursa (job #2169373) | Cod sursa (job #509858) | Cod sursa (job #1310148) | Cod sursa (job #2663953)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector <int> adiacenta[100000];
bool vizitat[100000] = {false};
void DFS(int nod)
{
vizitat[nod] = true;
for(int i=0; i< adiacenta[nod].size(); i++)
{
if(!vizitat[adiacenta[nod][i]])
{
DFS(adiacenta[nod][i]);
}
}
// for (auto it = adiacenta[nod].begin(); it != adiacenta[nod].end(); it++)
// {
// if(!vizitat[it])
// {
//
// DFS(it);
// }
//
// }
}
int main()
{
int N,M,x,y;
int nr_comp_conexe = 0;
in>>N>>M;
for(int i =1; i <=M ;i++)
{
in>>x>>y;
adiacenta[x].push_back(y);
//graf neorientat x y muchie => x e vecinul lui y si y e vecinul lui x
adiacenta[y].push_back(x);
}
for(int i = 1; i <= N; i++)
{
if(!vizitat[i])
{
nr_comp_conexe += 1;
DFS(i);
}
}
out<<nr_comp_conexe<<"\n";
return 0;
}