Pagini recente » clasament-arhiva-educationala | Borderou de evaluare (job #2005072) | Istoria paginii runda/parfum_de_iasomnie | Borderou de evaluare (job #2007044) | Cod sursa (job #2508194)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n;
vector<int> G[100001];
bool viz[100001];
void DFS(int i);
int main(){
int m;
in>>n>>m;
for(int i = 1; i <= m; i++){
int x, y;
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
int k = 0;
for(int i = 1; i <= n; i++){
if(viz[i] == false){
DFS(i);
k++;
}
}
out<<k;
return 0;
}
void DFS(int i){
stack<int> s;
s.push(i);
while(!s.empty()){
int n = s.top();
s.pop();
viz[n] = true;
for(int j = 0; j < G[n].size(); j++){
int succ = G[n].at(j);
if(viz[succ] == false){
s.push(succ);
}
}
}
}