Pagini recente » Cod sursa (job #454503) | Cod sursa (job #487092) | Cod sursa (job #852430) | Cod sursa (job #373632) | Cod sursa (job #2532101)
#include <iostream>
#include<fstream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
bool parcurs[100001];
vector<int>graf[100001];
void DFS(int nod){
stack<int>s;
s.push(nod);
while(!s.empty()){
int top = s.top();
s.pop();
if(parcurs[top] == false){
parcurs[top] = true;
for(int i = 0; i<graf[top].size(); ++i){
s.push(graf[top][i]);
}
}
}
}
void DFS_recursiv(int nod){
parcurs[nod] = true;
for(int i = 0; i<graf[nod].size(); ++i){
int vecin = graf[nod][i];
if(parcurs[vecin] == 0)
DFS_recursiv(vecin);
}
}
int main()
{
in>>n>>m;
while(m--){
int a, b;
in>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a); ///graful e neorientat
}
int nr_componente = 0;
for(int i = 1; i<=n; ++i){
if(parcurs[i] == false){
++nr_componente;
DFS_recursiv(i);
}
}
out<<nr_componente;
in.close();
out.close();
return 0;
}