Pagini recente » Cod sursa (job #2220356) | Cod sursa (job #2236316) | Cod sursa (job #381379) | Cod sursa (job #2678077) | Cod sursa (job #682249)
Cod sursa(job #682249)
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");
struct dfsearch{
vector<int> next;
bool done;
dfsearch(){
done=0;
}
};
int main(){
int n , m;
vector<dfsearch> graf;
vector<int> coada;
fi>>n>>m;
for(int i=0;i<n;i++)
graf.push_back(dfsearch());
for(int i=0;i<m;i++){
int x , y;
fi>>x>>y;
graf[x-1].next.push_back(y-1);
graf[y-1].next.push_back(x-1);
}
int k=0;
for(int i=0;i<n;i++){
if(!graf[i].next.size()&&!graf[i].done){graf[i].done=1;k++;continue;}
if(graf[i].done){continue;}
if(!graf[i].done){k++;graf[i].done=1;}
for(int j=0;j<(signed)graf[i].next.size();j++){
coada.push_back(graf[i].next[j]);
}
int j=0;
while(j!=(signed)coada.size()){
graf[coada[j]].done=1;
for(int l=0;l<(signed)graf[coada[j]].next.size();l++){
if(!graf[graf[coada[j]].next[l]].done)
coada.push_back(graf[coada[j]].next[l]);
graf[graf[coada[j]].next[l]].done=1;
}
j++;
}
coada.clear();
}
fo<<k;
}