Pagini recente » Cod sursa (job #1289966) | Cod sursa (job #1240540) | Cod sursa (job #828914) | Cod sursa (job #1175649) | Cod sursa (job #629912)
Cod sursa(job #629912)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N=100001;
struct comp{
int nod,nrvec;
}stack[N];
vector <int> muchie[N];
int n,m,compcon,stacksize;
bool viz[N];
void citire(){
int i,x,y;
in>>n>>m;
for(i=1;i<=n;++i){
in>>x>>y;
muchie[x].push_back(y);
muchie[y].push_back(x);
}
}
void DFS(int x){
int i,nod,ok;
nod=x;
stacksize++;
stack[stacksize].nod=x;
stack[stacksize].nrvec=0;
while(stacksize!=0){
nod=stack[stacksize].nod;
viz[nod]=true;
ok=0;
for(i=stack[stacksize].nrvec;i<muchie[nod].size();++i){
if(!viz[muchie[nod][i]]){
stacksize++;
stack[stacksize].nod=muchie[nod][i];
stack[stacksize].nrvec=0;
ok=1;
break;
}
}
if(!ok){
stacksize--;
}
}
}
void rezolvare(){
int i;
for(i=1;i<=n;++i){
if(!viz[i]){
compcon++;
DFS(i);
}
}
}
int main(){
citire();
rezolvare();
out<<compcon;
return 0;
}