Pagini recente » Cod sursa (job #2806780) | Cod sursa (job #1236494) | Cod sursa (job #2418262) | Cod sursa (job #1325074) | Cod sursa (job #2853913)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int mAdiacenta[1000][1000];
int vizitat[1000];
int N, M; //N - numarul de noduri M - numarul de muchii
bool Parcurs(int freq[], int noduri)
{
for (int i = 1; i <= noduri; i++)
if(freq[i] == 0)
return false;
return true;
}
void DFS(int nod, int noduri)
{
vizitat[nod] = 1;
for (int i = 1; i <= noduri; i++)
{
if(vizitat[i] == 0 && mAdiacenta[nod][i] == 1)
{
vizitat[i] = 1;
DFS(i,noduri);
}
}
}
int main()
{
in >> N >> M;
int x, y;
for (int i = 0; i < M; i++)
{
in >> x >> y;
mAdiacenta[x][y] = 1;
mAdiacenta[y][x] = 1;
}
int conexe = 0;
for (int i = 1; i <= N; i++)
{
if(vizitat[i] == 0)
{
DFS(i,N);
conexe++;
}
}
out << conexe;
return 0;
}