Pagini recente » Istoria paginii runda/oni_10_0/clasament | Cod sursa (job #2797959) | Istoria paginii runda/sim_oni_2010_ziua1/clasament | Cod sursa (job #2096972) | Cod sursa (job #2797462)
#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);
}
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;
}