Cod sursa(job #2858084)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 26 februarie 2022 22:23:24
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define MAXN 100001

struct nod {
    int subset;
    vector<int> edges;
};
nod nodes[MAXN];

void adauga(int a, int b) {
    nodes[a].edges.push_back(b);
    nodes[b].edges.push_back(a);
}

void dfs(int i, int subset) {
    nodes[i].subset = subset;
    for (int vecin : nodes[i].edges) {
        if (nodes[vecin].subset != subset) {
            dfs(vecin, subset);
        }
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("dfs.in", "r");
    fout = fopen("dfs.out", "w");
    
    int n, m, i, a, b, nr;
    
    fscanf(fin, "%d%d", &n, &m);
    
    for (i=0; i<m; i++) {
        fscanf(fin, "%d%d", &a, &b);
        adauga(a, b);
    }
    
    nr=0;
    for (i=0; i<n; i++) {
        if (nodes[i].subset == 0)
            dfs(i, nr++);
    }
    
    fprintf(fout, "%d\n", nr);
    
    fclose(fin);
    fclose(fout);
    return 0;
}