Pagini recente » Cod sursa (job #2427317) | Cod sursa (job #2917397) | Cod sursa (job #682005) | Cod sursa (job #269268) | Cod sursa (job #801352)
Cod sursa(job #801352)
#include <fstream>
using namespace std ;
struct nod {int nr;nod *adr;} ;
nod *v[100001] ;
long n,m ;
int viz[100001] ;
ofstream g ;
nod *nou (int nr) {
nod *aux=new nod ;
aux->nr=nr ;
aux->adr=NULL ;
return aux ;
}
void adaugare (nod *&a,long nr) {
nod *aux=nou(nr) ;
aux->adr=a ;
a=aux ;
}
void citire () {
long x,y,i ;
for (i=1;i<=n;i++) v[i]=NULL ;
ifstream f ("dfs.in") ;
f>>n>>m ;
for (i=1;i<=m;i++) {
f>>x>>y ;
adaugare(v[x],y) ;
adaugare(v[y],x) ;
}
f.close() ;
}
/*void afisare (nod *p) {
while (p) {
g<<p->nr<<' ' ;
p=p->adr ;
}
g<<endl ;
}*/
void dislocare (nod *p) {
nod *aux ;
while (p) {
aux=p->adr ;
delete p ;
p=aux ;
}
}
void dfs (int x) {
int s[100001],vf ;
s[1]=x;vf=1;viz[x]=1;
while (vf>0) {
while (v[s[vf]]) {
if (viz[v[s[vf]]->nr]==0) {s[vf+1]=v[s[vf]]->nr;viz[v[s[vf]]->nr]=1;vf++;break;}
v[s[vf]]=v[s[vf]]->adr ;
}
if (!v[s[vf]]) vf-- ;
}
}
int main () {
long i,nr=0 ;
citire() ;
for (i=1;i<=n;i++)
if (viz[i]==0) {
nr++ ;
dfs(i) ;
}
g.open("gfs.out") ;
g<<nr ;
g.close() ;
for (i=1;i<=n;i++) dislocare(v[i]) ;
return 0 ;
}