Cod sursa(job #976095)

Utilizator Tux2NicolaeTelechi Nicolae Tux2Nicolae Data 22 iulie 2013 15:45:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>
#define DIM 100003
int n,m,res;

typedef struct list{
    int node;
    list* next;
} *List;

List graph[DIM];
bool visited[DIM];

void add(int from,int to){
    List temp;

    temp=new list;
    temp->node=to;
    temp->next=graph[from];
    graph[from]=temp;
}

void read_data(){
    int i,x,y;
    scanf("%d %d",&n,&m);
    for(i=0;i<m;++i){
        scanf("%d %d",&x,&y);
        add(x,y);
        add(y,x);
    }
}

void dfs(int s){
    List it;

    it=graph[s];
    visited[s]=true;
    while(it!=NULL){
        if(!visited[it->node]){
            visited[it->node]=true;
            dfs(it->node);
        }
        it=it->next;
    }
}

void solve(){
    int i;
    for(i=1;i<=n;i++){
        if(!visited[i]){
            dfs(i);
            ++res;
        }
    }
}

void write_data(){
    printf("%d\n",res);
}

int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    read_data();
    solve();
    write_data();

    return 0;
}