Pagini recente » Cod sursa (job #1028918) | Cod sursa (job #2313261) | Cod sursa (job #2705174) | Cod sursa (job #2751592) | Cod sursa (job #2822469)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#define NMax 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
class graf
{
private:
int n, m;
bool vizitate[100001];
vector <int> adj_list[100001];
public:
graf(int n, int m);
void citire_neorientat_adj_list();
void DFS(int s);
void conexe();
};
graf::graf(int n, int m)
{
this->n = n;
this->m = m;
}
void graf::citire_neorientat_adj_list()
{
for(int i = 1; i <= m; ++i)
{ int nod1, nod2;
f>>nod1>>nod2;
adj_list[nod1].push_back(nod2);
adj_list[nod2].push_back(nod1);
}
}
void graf::DFS(int start_node)
{
vizitate[start_node] = 1;
for(int i : adj_list[start_node])
if(!vizitate[i])
DFS(i);
}
void graf::conexe()
{
int nr_comp = 0;
for(int i = 1; i <= n; ++i)
if(!vizitate[i])
{
nr_comp=nr_comp+1;;
DFS(i);
}
g<< nr_comp;
}
int main()
{
int n,m;
f>>n>>m;
graf G(n, m);
G.citire_neorientat_adj_list();
G.conexe();
return 0;
}