Pagini recente » Borderou de evaluare (job #2649063) | Cod sursa (job #686832) | Cod sursa (job #748358) | Cod sursa (job #515000) | Cod sursa (job #3253191)
#include <fstream>
using namespace std;
#include <vector>
ifstream fin("dfs.in");
ofstream fout("dfs.out");
std::vector <std::vector<int>> lista;
std::vector <bool> viz;
void Construieste(int N, int M)
{
int x, y;
for(int i = 0; i < M; i++)
{
fin >> x >> y;
lista[x - 1].push_back(y - 1);
lista[y - 1].push_back(x - 1);
}
}
void DFS(int nod)
{
viz[nod] = 1;
int size = lista[nod].size();
for(int i = 0; i < size; i++)
if(!viz[lista[nod][i]])
DFS(lista[nod][i]);
}
int main() {
int N, M;
fin >> N >> M;
lista.resize(N);
Construieste(N, M);
viz.resize(N, 0);
int componente_conexe = 0;
for(int i = 0; i < N; i++)
if(!viz[i])
{
DFS(i); componente_conexe ++;
}
fout << componente_conexe;
}