Pagini recente » Cod sursa (job #305135) | Cod sursa (job #545660) | Cod sursa (job #2635195) | Cod sursa (job #533455) | Cod sursa (job #2542418)
#include<fstream>
#include<stack>
#include<vector>
#define NMAX 100005
//in-out
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
//data
std::vector<int>G[NMAX];
std::stack<int>st;
std::vector<bool> visited(NMAX);
int n, m;
void readData(){
f >> n >> m;
int x, y;
for(int i = 0; i<m; i++){
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int start){
visited[start] = true;
for(const auto& adj : G[start]){
if(!visited[adj]){
dfs(adj);
}
}
}
int connectedComponents(){
int nrComps = 1;
dfs(1);
for(int i = 2; i<=n; i++){
if(!visited[i]){
nrComps += 1;
dfs(i);
}
}
return nrComps;
}
int main(){
readData();
g << connectedComponents();
return 0;
}