Pagini recente » Clasament ichcposdi | Cod sursa (job #2614308) | Cod sursa (job #1975378) | Cod sursa (job #2547654) | Cod sursa (job #2697701)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 10000
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,x,y,nr_elem_comp;
bool viz[NMAX];
//vector in care stocam elementele(lista de vecini)
vector<int>vecini[NMAX];
void DFS(int s)
{
int s2;
//marcam nodul in care suntem ca vizitat
viz[s]=1;
//parcurgem vecinii nodului in care am intrat (nodului curent)
for(unsigned int i=0; i<vecini[s].size(); i++)
{
s2=vecini[s][i];//s2 ia valoare vecinului
//daca vecinul nu este vizitat , facem DFS de vecin
if(!viz[s2])
{
DFS(s2);
}
}
}
int main()
{
f>>n>>m;
//citim din fisier elementele
for(int i=1; i<=m; i++)
{//avem graf neorientat , deci avem muchie in ambele sensuri
f>>x>>y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
for(int i=1; i<=n; i++)
{
if(!viz[i])
{
nr_elem_comp++;
DFS(i);
}
}
cout<<nr_elem_comp;
return 0;
}