Pagini recente » Istoria paginii runda/23zile_1 | Cod sursa (job #1006509) | Atasamentele paginii Clasament 1212121 | Istoria paginii runda/123455 | Cod sursa (job #2797567)
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("dfs.in");
ofstream o("dfs.out");
class Graph
{
vector<bool> vis;
vector<vector<int>> adjList;
int size;
public:
Graph(int n)
{
size = n + 1;
adjList.resize(size);
for (int i = 1; i <= size; i++)
vis.push_back(false);
}
void addEdge(int start, int end)
{
adjList[start].push_back(end);
adjList[end].push_back(start);
}
void DFS(int node)
{
vis[node] = true;
for (auto i : adjList[node])
if (!vis[i])
DFS(i);
}
int Connected()
{
int k = 0;
for (int i = 1; i <= size - 1; i++)
if (!vis[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;
}