Cod sursa(job #624408)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 22 octombrie 2011 12:28:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>

struct nod{
    int x;
    struct nod*next; } *v[100001];
bool viz[100001];
int n,m,r;

void add(int x,int y){
    nod*s;
    s=new nod;
    s->x=y;
    s->next=v[x];
    v[x]=s;
}

void dfs(int x){
    nod*s=v[x];
    viz[x]=1;
    while(s!=NULL){if(!viz[s->x])dfs(s->x);s=s->next;}
}

int main(){
    int i,x,y;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x); }
    for(i=1;i<=n;i++)
    if(!viz[i]){r++;dfs(i);}
        printf("%d\n",r);
}