Cod sursa(job #1417289)

Utilizator mariusadamMarius Adam mariusadam Data 10 aprilie 2015 00:13:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>
#define nmax 100001

using namespace std;

struct Nod {
    int nd;
    Nod *next;
};

Nod *G[nmax];

void getData(Nod *G[nmax],int &n,int &m) {

    ifstream r("dfs.in");
    r>>n>>m;
    for (int k=1;k<=m;k++){
        int i,j;
        Nod *p;
        r>>i>>j;
        p=new Nod;
        p->next=G[i];
        p->nd=j;
        G[i]=p;
        p=new Nod;
        p->next=G[j];
        p->nd=i;
        G[j]=p;
    }
    r.close();
}

void dfs(int x,bool (&viz)[nmax]) {
    Nod *p;
    viz[x]=true;
    p=G[x];
    while (p) {
        if (!viz[p->nd])
            dfs(p->nd,viz);
        p=p->next;
    }
}

int nrComp(Nod *G[nmax],int n) {
    int nr=0,i;
    bool viz[nmax];

    memset(viz,false,sizeof(viz));
    for(i=1;i<=n;i++)
        if (!viz[i]){
        nr++;
        dfs(i,viz);
        }
    return nr;
}

void print(int x) {

    ofstream w("dfs.out");
    w<<x<<endl;
    w.close();
}

int main () {
    int n,m;

    getData(G,n,m);
    print(nrComp(G,n));
    return 0;
}