Pagini recente » Borderou de evaluare (job #1697610) | Borderou de evaluare (job #1915206) | Cod sursa (job #2636127) | Borderou de evaluare (job #1234044) | Cod sursa (job #2782412)
/*
Alexandru Enache
Grupa 252
*/
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("input"); ofstream fout("output");
ifstream fin("dfs.in"); ofstream fout("dfs.out");
class Graph{
private:
int m_nodes;
vector < vector < int > > m_gr;
public:
Graph(int nodes, vector < vector < int > > &gr){
m_nodes = nodes;
m_gr = gr;
}
vector < int > bfs(int start){
queue < int > q;
vector < int > dist(m_nodes, -1);
dist[start] = 0;
q.push(start);
while (!q.empty()){
int now = q.front();
q.pop();
for (auto &x : m_gr[now]){
if (dist[x] == -1){
dist[x] = dist[now] + 1;
q.push(x);
}
}
}
return dist;
}
void dfs(int node, vector < bool > &used){
used[node] = true;
for (auto &x: m_gr[node]){
if (!used[x]){
dfs(x, used);
}
}
}
int comp_conex_dfs(){
int cont = 0;
vector < bool > used(m_nodes, false);
for (int i=0; i<m_nodes; i++){
if (!used[i]){
dfs(i, used);
cont++;
}
}
return cont;
}
};
void solve() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m;
fin>>n>>m;
vector < vector < int > > gr(n);
for (int i=1; i<=m; i++){
int a, b;
fin>>a>>b;
a--;
b--;
gr[a].push_back(b);
gr[b].push_back(a);
}
Graph graph = Graph(n, gr);
int comp_conex = graph.comp_conex_dfs();
fout<<comp_conex<<'\n';
}
int main() {
solve();
return 0;
}