Cod sursa(job #548445)

Utilizator maryiiroman mariana maryii Data 7 martie 2011 14:26:52
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream.h>
#define NM 100001

ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct nod{ int nr; nod*next;};
nod *l[NM],*urm[NM];
int n,m,s[NM],viz[NM],cc;

void add(nod*&l,int x){
     nod*nn=new(nod);
     nn->nr=x;
     nn->next=l;
     l=nn;
     }
void build(){
     int i,x,y;
     fin>>n>>m;
     for(i=1;i<=m;i++){ fin>>x>>y;
			add(l[x],y);
			add(l[y],y);
			}
     }
void df(int x){
     int y;
     nod *nc=urm[x];
     while(nc){ viz[x]=cc;
		y=nc->nr;
		nc=nc->next;
		if(!viz[y])
		df(y);
		urm[x]=nc;
		}
     }
int main(){
    int i;
    build();
    for(i=1;i<=n;i++)
    urm[i]=l[i];
    for(i=1;i<=n;i++)
    if(!viz[i]) {cc++; df(i); }
    fout<<cc;
    return 0;
    }