Pagini recente » Cod sursa (job #761649) | Cod sursa (job #2431936) | Cod sursa (job #2842514) | Cod sursa (job #282892) | Cod sursa (job #1347044)
//componente conexe
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using namespace std;
int main(){
ifstream ifs("dfs.in");
ofstream ofs("dfs.out");
int N,M;
ifs>>N>>M;
vector<list<int > > v(N);
for(int i=0;i<M;i++){
int t; ifs>>t; t--;
v[i].push_back(t);
v[t].push_back(i);
}
int sol=0;
vector<bool> m(N,false);
for(int i=0;i<N;i++){
if(!m[i]){ //DFS
stack<int> s; s.push(i);
while(!s.empty()){
int f=s.top(); s.pop();
if(!m[f]){
m[f]=true;
for(list<int>::iterator j=v[f].begin();j!=v[f].end();j++)
s.push(*j);
}
}
sol++;
}
}
ofs<<sol;
}