Pagini recente » Cod sursa (job #1433789) | Cod sursa (job #3179475) | Cod sursa (job #688348) | Cod sursa (job #2641359) | Cod sursa (job #369689)
Cod sursa(job #369689)
#include<fstream>
using namespace std;
#define endl '\n'
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,cc,viz[100001],st[100001];
struct nod{
int inf;
nod *adr;
};
struct lista{
nod *vf,*sf;
};
lista v[100001];
nod *uv[100001];
void add(lista &l,int x){
nod *n=new nod;
n->inf=x;
n->adr=NULL;
if(!l.vf) l.vf=n;
else l.sf->adr=n;
l.sf=n;
}
void dfs(int start){
int k=1,up;
nod *nc;
st[k]=start;
viz[st[k]]=cc;
nc=v[start].vf;
while(nc&&viz[nc->inf]) nc=nc->adr;
if(nc) uv[1]=nc;
else return;
while(k){
up=0;
while(!up&&nc){
nc=uv[k];
while(nc&&viz[nc->inf]) nc=nc->adr;
if(nc) up=1;
}
if(up){
uv[k]=nc;
k++;
st[k]=nc->inf;
viz[nc->inf]=cc;
uv[k]=v[nc->inf].vf;
}
else {
k--;
nc=uv[k];
}
}
}
int main(){
fin>>n>>m;
int i,x,y;
for(i=1;i<=m;i++){
fin>>x>>y;
add(v[x],y);
add(v[y],x);
}
for(i=1;i<=n;i++)
if(!viz[i]){
cc++;
dfs(i);
}
fout<<cc;
return 0;
}