Mai intai trebuie sa te autentifici.
Cod sursa(job #629915)
Utilizator | Data | 4 noiembrie 2011 10:24:26 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.99 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N=300010;
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;
}