Cod sursa(job #3241737)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 3 septembrie 2024 12:00:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

const int NMAX = 100000;

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

nod *L[NMAX+1];
int N, M;
bool viz[NMAX+1];

void add_nod(int x, int y) {
    nod *p = new nod;
    p -> x = y;
    p -> next = L[x];
    L[x] = p;
}

void citire() {
    int x, y;
    f >> N >> M;
    for (int i=1; i<=M; i++) {
        f >> x >> y;
        add_nod(x, y);
        add_nod(y, x);
    }
}

void DFS(int i) {
    viz[i] = 1;
    for (nod *p = L[i]; p != NULL; p=p->next)
        if (!viz[p->x])
            DFS(p->x);
}

int main()
{
    int nrCC = 0;
    citire();
    for (int i=1; i<=N; i++)
        if (!viz[i]) {
            DFS(i);
            nrCC++;
        }
    g << nrCC << '\n';
    f.close();
    g.close();
    return 0;
}