Pagini recente » Cod sursa (job #597507) | Cod sursa (job #99680) | Cod sursa (job #462591) | Cod sursa (job #773595) | Cod sursa (job #1141629)
#include <fstream>
#include <vector>
using namespace std;
class DFS
{
private:
struct node
{
vector<int> vecini;
bool vizitat;
} *noduri;
int nrNoduri, nrMuchii;
public:
DFS();
int compConexe();
private:
void parcurgeDFS(int i);
};
void DFS::parcurgeDFS(int i)
{
noduri[i].vizitat = true;
for (auto& it : noduri[i].vecini)
if (noduri[it].vizitat == false) parcurgeDFS(it);
}
int DFS::compConexe()
{
int componente = 0;
for (int i = 1; i <= nrNoduri; i++)
if(!noduri[i].vizitat)
parcurgeDFS(i), componente++;
return componente;
}
DFS::DFS()
{
ifstream IN("dfs.in");
IN >> nrNoduri >> nrMuchii;
noduri = new node[nrNoduri + 1];
for (int i = 1; i <= nrNoduri; i++)
noduri[i].vizitat = false;
for (int i = 1 ; i <= nrMuchii; i++)
{
int x, y;
IN >> x >> y;
noduri[x].vecini.push_back(y);
noduri[y].vecini.push_back(x);
}
IN.close();
}
int main()
{
DFS graf;
ofstream OUT("dfs.out");
OUT << graf.compConexe();
OUT.close();
return 0;
}