Pagini recente » Cod sursa (job #2799954) | Cod sursa (job #2158939) | Cod sursa (job #2982094) | Cod sursa (job #2647697) | Cod sursa (job #2202546)
#include <fstream>
#include <vector>
#include <deque>
#define NMAX 100005
#define pb push_back
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m;
vector<int>G[NMAX];
bool viz[NMAX];
void read_data(int &n, int &m){
f >> n >> m;
for(int i = 1; i<=m; i++){
int x, y;
f >> x >> y;
G[x].pb(y);
G[y].pb(x);
}
}
void dfs(vector<int> G[], int src){
viz[src] = true;
for(int i = 0; i<G[src].size(); i++){
if(!viz[G[src][i]]){
dfs(G, G[src][i]);
}
}
}
int conex_comp(vector<int>G[]){
int nrc = 1;
dfs(G, 1);
for(int i = 1; i<=n; i++){
if(!viz[i]){
nrc++;
dfs(G, i);
}
}
return nrc;
}
int main(){
read_data(n, m);
g << conex_comp(G);
return 0;
}