Cod sursa(job #1892158)

Utilizator AsttridMocanu Ada Astrid Asttrid Data 24 februarie 2017 19:16:02
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int oo=100002;
struct nod{int inf;
nod*urm;};
nod*L[oo];
int n,m,viz[oo],nrc=1;

inline void citire(){
in>>n>>m;
int i,x,y;
nod *p;
for(i=1;i<=m;i++)
{in>>x>>y;
p=new nod;
p->inf=y;
p->urm=L[x];
L[x]=p;
p=new nod;
p->inf=x;
p->urm=L[y];
L[y]=p;
}
}

inline void dfs(int x){
int st[oo],top,y,g;
nod*q;
viz[x]=nrc;
top=1;
st[top]=x;
while(top){
    y=st[top];
    q=L[y];
    g=0;
    while(q){
if(!viz[q->inf]){
    viz[q->inf]=nrc;
    st[++top]=q->inf;g=1;break;
}
q=q->urm;
    }
    if(g==0)top--;}
}


inline void rez(){
int x,i,g;
x=1;
do{g=0;dfs(x);
for(i=1;i<=n;i++)
if(!viz[i]){x=i;nrc++;g=1;break;}
}while(g);
out<<nrc<<"\n";

}

int main(){
citire();
rez();
in.close();
out.close();
return 0;}