Cod sursa(job #1879902)

Utilizator Constantin.Dragancea Constantin Constantin. Data 15 februarie 2017 11:21:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

struct nod{
    nod *next;
    int data;
};

bool B[100100];
int n,m,k,x,y;
nod *A[100100];

void add(int x, int y){
    nod *r, *w;
    r=new nod; w= new nod;
    r->data=x; w->data=y;
    r->next=NULL; w->next=NULL;
    if(!A[y]) A[y]=r;
    else{       r->next = A[y];      A[y]=r;}
    if(!A[x]) A[x]=w;
    else{   w->next = A[x];  A[x]=w;}
    //if (A[x]==0) A[x]=w;
    //else {w->next=A[x]; A[x]=w;}
    //if (A[y]==0) A[y]=r;
    //else {r->next=A[x]; A[y]=r;}
}

void dfs(int i){
    if (!B[i]) B[i]=true;
    while (A[i]!=NULL){
        nod *r;
        r=A[i];
        A[i]=A[i]->next;
        if (!B[r->data]) B[r->data]=true;
        dfs(r->data);
    }
}

int main(){
	ifstream cin ("dfs.in");
	ofstream cout ("dfs.out");
    cin>>n>>m;
    for (int i=1; i<=m; i++){
        cin>>x>>y;
        add(x,y);
    }
    for (int i=1; i<=n; i++){
        if (!B[i]){
            dfs(i);
            k++;
        }
    }
    cout<<k;
    return 0;
}