Pagini recente » Cod sursa (job #201355) | Cod sursa (job #1686548) | Cod sursa (job #2783242) | Cod sursa (job #164591) | Cod sursa (job #2919056)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph{
private:
int n_nodes;
vector<bool> visited;
vector<vector<int>> adj;
int no_comp_conexe = 0;
public:
Graph(){
n_nodes = 0;
adj = {};
}
Graph(int n, vector<vector<int>> &graph)
{
n_nodes = n;
adj = graph;
visited.resize(n+1, false);
}
void dfs(int root);
void dfs_comp_conexe(int root);
int comp_conexe();
};
void Graph::dfs(int root)
{
visited[root] = true;
for(int i = 0; i < adj[root].size(); ++i)
{
if(!visited[adj[root][i]]){
dfs(adj[root][i]);
cout<<adj[root][i]<<' ';
}
}
}
void Graph::dfs_comp_conexe(int root)
{
visited[root] = true;
for(int i = 0; i < adj[root].size(); ++i)
{
if(!visited[adj[root][i]]){
dfs(adj[root][i]);
}
}
no_comp_conexe++;
}
int Graph::comp_conexe()
{
for(int i = 1; i <= n_nodes; ++i){
if(!visited[i]) dfs_comp_conexe(i);
}
return no_comp_conexe;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, x, y;
vector<vector<int>> a;
fin>>n>>m;
a.resize(n+1);
for(int i = 0; i < m; ++i)
{
fin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
//cout<<x<<' '<<y<<' ';
}
Graph g(n, a);
fout<<g.comp_conexe();
return 0;
}