Cod sursa(job #3148872)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 4 septembrie 2023 19:55:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int MAX_LENGTH = 100000;

int fr[MAX_LENGTH + 1];
int counter;

struct {
    vector<int> nodeEnd;
} nodeStart[MAX_LENGTH + 1];

void gen(int nodesLen, int edgesLen, int node) {
    for (vector<int>::iterator it = nodeStart[node].nodeEnd.begin(); it < nodeStart[node].nodeEnd.end(); ++it) {
        if (fr[*it] == 0) {
            fr[*it] = 1;
            gen(nodesLen, edgesLen, *it);
        }
    }
}

int main() {
    int nodesLen, edgesLen;
    fin >> nodesLen >> edgesLen;
    for (int i = 1; i <= edgesLen; ++i) {
        int node1, node2;
        fin >> node1 >> node2;
        nodeStart[node1].nodeEnd.push_back(node2);
        nodeStart[node2].nodeEnd.push_back(node1);
    }
    for (int node = 1; node <= nodesLen; ++node) {
        if (fr[node] == 0) {
            ++counter;
        }
        gen(nodesLen, edgesLen, node);
    }
    fout << counter;
    return 0;
}
/*
 
 */