Pagini recente » Cod sursa (job #603566) | Cod sursa (job #1517196) | Cod sursa (job #1702356) | Cod sursa (job #2218518) | Cod sursa (job #1932648)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin ("dfs.in");
ofstream cout ("dfs.out");
class GrafNeorientat
{
int nrNoduri, nrMuchii;
vector<int> muchii[100001];
public:
int GetNrNoduri()
{
return nrNoduri;
}
int GetNrMuchii()
{
return nrMuchii;
}
void CitesteGraf()
{
cin >> nrNoduri >> nrMuchii ;
for(int i = 1; i <= nrMuchii; ++i)
{
int nod1, nod2;
cin >> nod1 >> nod2;
muchii[nod1].push_back(nod2);
muchii[nod2].push_back(nod1);
}
}
vector<int> BFS(int nodStart)
{
queue<int> q;
q.push(nodStart);
vector<int> dist;
for(int i = 0 ; i <= nrNoduri; ++i)
{
dist.push_back(0);
}
while(!q.empty())
{
int nod = q.front();
for(int i = 0; i < muchii[nod].size(); ++i)
{
int vecin = muchii[nod][i];
if(vecin == nodStart)
{
continue;
}
if(dist[vecin] == 0)
{
q.push(vecin);
dist[vecin] = dist[nod] + 1;
}
}
q.pop();
}
return dist;
}
void DFS(int nod, vector<bool> &viz)
{
viz[nod] = true;
for(int i = 0; i < muchii[nod].size(); ++i)
{
int vecin = muchii[nod][i];
if(!viz[vecin])
{
DFS(vecin, viz);
}
}
}
int ComponenteConexe()
{
vector<bool> viz;
for(int i = 0; i <= nrNoduri; ++i)
{
viz.push_back(false);
}
int nr = 0;
for(int i = 1; i <= nrNoduri; ++i)
{
if(!viz[i])
{
DFS(i, viz);
++nr;
}
}
cout << nr;
return nr;
}
void MatriceaDrumurilor()
{
}
};
int main()
{
GrafNeorientat graf;
graf.CitesteGraf();
graf.ComponenteConexe();
return 0;
}