Pagini recente » Cod sursa (job #2541249) | Cod sursa (job #278444) | Cod sursa (job #2322317) | Cod sursa (job #2357274) | Cod sursa (job #2335014)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned int uint;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph
{
uint V;
vector<vector<uint>> adj;
void DFS(uint node, vector<bool> &v);
public:
Graph(const uint V);
void Add_edge(uint x, uint y);
uint NrOfComps();
};
Graph::Graph(const uint V)
{
this->V = V;
adj.assign(V + 1, vector<uint>());
}
void Graph::Add_edge(uint x, uint y)
{
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
void Graph::DFS(uint node, vector<bool> &v)
{
v[node] = true;
for (auto &i : adj[node])
{
if (!v[i])
DFS(i,v);
}
}
uint Graph::NrOfComps()
{
uint nr = 0;
vector<bool> v(V + 1, false);
for (uint i = 1; i <= V; ++i)
{
if (!v[i])
{
++nr;
DFS(i,v);
}
}
return nr;
}
int main()
{
uint n,m;
fin >> n >> m;
Graph G(n);
for (uint x,y, i = 0; i < m; ++i)
{
fin >> x >> y;
G.Add_edge(x,y);
}
fout << G.NrOfComps();
}