Cod sursa(job #2438290)

Utilizator Horia14Horia Banciu Horia14 Data 12 iulie 2019 00:41:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include<cstdio>
#define MAX_N 100000
using namespace std;

struct node {
    int val;
    node* next;
};

node* g[MAX_N+1];
bool used[MAX_N+1];
int n, m, nrc;

void insertEdge(int x, int y) {
    node* elem = new node;
    elem->val = y;
    elem->next = g[x];
    g[x] = elem;
}

void readGraph() {
    int i, x, y;
    FILE* fin = fopen("dfs.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i = 0; i < m; i++) {
        fscanf(fin,"%d%d",&x,&y);
        insertEdge(x,y);
        insertEdge(y,x);
    }
    fclose(fin);
}

void DFS(int x) {
    used[x] = true;
    node* p = g[x];
    while(p != NULL) {
        if(!used[p->val])
            DFS(p->val);
        p = p->next;
    }
}

void DFS_master() {
    int i;
    nrc = 0;
    for(i = 1; i <= n; i++) {
        if(!used[i]) {
            DFS(i);
            nrc++;
        }
    }
}

void printNrc() {
    FILE* fout = fopen("dfs.out","w");
    fprintf(fout,"%d\n",nrc);
    fclose(fout);
}

int main() {
    readGraph();
    DFS_master();
    printNrc();
    return 0;
}