Cod sursa(job #148786)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 4 martie 2008 20:30:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#define FIN "dfs.in"
#define FOUT "dfs.out"
#define MAX_N 100000
using namespace std;
struct list{
        int inf;
        list* urm;
} *g[MAX_N+1];
int n,m;
int used[MAX_N+1];


void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        scanf("%d%d",&n,&m);
        int x,y;
        list* q;
        for (int i=1;i<=m;i++){
                scanf("%d%d",&x,&y);
                q=new list;q->inf=y;q->urm=g[x];g[x]=q;
                q=new list;q->inf=x;q->urm=g[y];g[y]=q;
        }
        fclose(stdin);
}



void dfs(int nod){
        for (list* q=g[nod];q;q=q->urm){
                if (!used[q->inf]){
                        used[q->inf]=1;
                        dfs(q->inf);
                }
        }
}

void solve(void){
        int nrcomp=0;
        for (int i=1;i<=n;i++){
                if (!used[i]){
                        used[i]=1;
                        nrcomp++;
                        dfs(i);
                }
        }
        printf("%d\n",nrcomp);
        fclose(stdout);
}

int main(void){
        iofile();
        solve();
        return 0;
}