Pagini recente » Istoria paginii runda/iiot_5 | Diferente pentru calibrare-limite-de-timp intre reviziile 49 si 50 | Monitorul de evaluare | Diferente pentru calibrare-limite-de-timp intre reviziile 221 si 69 | Cod sursa (job #2797466)
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("dfs.in");
ofstream o("dfs.out");
class Graph
{
vector<bool> viz;
vector<vector<int>> adjList;
int size;
public:
Graph(int n)
{
size = n + 1;
adjList.resize(size);
for (int i = 1; i <= size; i++)
viz.push_back(false);
}
void addEdge(int start, int end)
{
adjList[start].push_back(end);
adjList[end].push_back(start);
}
void DFS(int node)
{
viz[node] = true;
for (auto i : adjList[node])
if (!viz[i])
DFS(i);
}
int Connected()
{
int k = 0;
for (int i = 1; i <= size - 1; i++)
if (!viz[i])
{
DFS(i);
k++;
}
return k;
}
};
int main()
{
int n, m;
int x, y;
f >> n >> m;
Graph g(n);
for (int i = 1; i <= m; i++)
{
f >> x >> y;
g.addEdge(x, y);
}
o<<g.Connected();
return 0;
}