Pagini recente » Cod sursa (job #1422391) | Cod sursa (job #2394988) | Cod sursa (job #1717585) | Cod sursa (job #1024197) | Cod sursa (job #2792288)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<bool> visited;
class Graph
{
private:
//number of nodes
int n;
//number of edges
int e;
//adj list for graph representation
vector<vector<int>> adj_list;
public:
Graph(int n)
{
this->n = n;
this->e = 0;
vector<int> empty;
for (unsigned int i = 0; i < n; i++)
{
this->adj_list.push_back(empty);
}
}
virtual ~Graph() {}
void add_edge(int node1, int node2)
{
this->e++;
this->adj_list[node1].push_back(node2);
this->adj_list[node2].push_back(node1);
}
void dfs(int start_node)
{
visited[start_node] = true;
for (unsigned int i = 0; i < adj_list[start_node].size(); i++)
{
int current_node;
current_node = adj_list[start_node][i];
if (visited[current_node] == false)
{
dfs(current_node);
}
}
}
};
int main()
{
int cnt = 0;
//number of nodes
int N;
//number of edges
int E;
fin >> N >> E;
Graph graph(N);
int n1, n2;
for (unsigned int i = 0; i < E; i++)
{
fin >> n1 >> n2;
graph.add_edge(n1 - 1, n2 - 1);
}
for (unsigned int i = 0; i < N; i++)
{
visited.push_back(false);
}
for (unsigned int i = 0; i < N; i++)
{
if (!visited[i])
{
cnt++;
graph.dfs(i);
}
}
fout << cnt;
return 0;
}