Cod sursa(job #1094880)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 29 ianuarie 2014 22:53:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<iostream>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

struct node{
    int info;
    node *next;
}* a[100005];


void add(node *&p, int info){
    node *r,*w;
    w=new node;
    r=new node;
    r->next=0;
    r->info=info;

    if(p==0)
        p=r;
    else{
        w=p;
        while(w->next){
            w=w->next;
        }
        w->next=r;
    }
}


bool b[100005];

void dfs(int x){
    b[x]=1;
    node *r;

    r=a[x];
    while(r){
        if(b[r->info]==0)
            dfs(r->info);
        r=r->next;
    }
}


int main(){
    int n,i,m,x,y,k=0;

    f>>n>>m;
    for(i=1; i<=m; ++i){
        f>>x>>y;
        add(a[x],y);
        add(a[y],x);
    }

    for(i=1; i<=n; ++i){
        if(b[i]==0){
            k++;
            dfs(i);
        }
    }

    g<<k;

return 0;
}