Pagini recente » Cod sursa (job #2786178) | Cod sursa (job #2891385) | Cod sursa (job #2649028) | Cod sursa (job #2765697) | Cod sursa (job #2786174)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph
{
private:
int cntNodes;
vector<vector<int>> adjList;
void dfs(int nodeId, bool visited[])
{
visited[nodeId] = true;
for (int childId : adjList[nodeId])
{
if (!visited[childId])
{
dfs(childId, visited);
}
}
}
public:
Graph(int n)
{
cntNodes = n;
for (int i = 0; i < n; ++i)
{
adjList.push_back(vector<int>());
}
}
void addEdge(int from, int to, bool oriented)
{
adjList[from].push_back(to);
if (!oriented)
{
adjList[to].push_back(from);
}
}
int countConnComp()
{
bool visited[cntNodes];
int cnt = 0;
for (int i = 0; i < cntNodes; ++i)
{
if (!visited[i])
{
++cnt;
dfs(i, visited);
}
}
return cnt;
}
};
int n, m, a, b;
int main()
{
fin >> n >> m;
Graph g(n);
while (m-- > 0)
{
fin >> a >> b;
g.addEdge(a - 1, b - 1, false);
}
fout << g.countConnComp();
return 0;
}