Cod sursa(job #3157913)

Utilizator flawreenFlorin Craciun flawreen Data 17 octombrie 2023 13:01:17
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

vector<int> vecini[100001];
int n, m, viz[101] = { 0 }, d[101] = { 0 }, tata[101] = { 0 };

void dfs(int s) {
    viz[s] = 1;
    for (int i = 1; i <= n; ++i) { // verific pentru fiecare nod daca e vecin nevizitat pt s
        if (viz[i] == 0 && find(vecini[s].begin(), vecini[s].end(), i) != vecini[s].end()) {
            tata[i] = s;
            d[i] = d[s] + 1;
            dfs(i);
        }
    }
}

int compConexe() {
    int rez = 0;
    for (int i = 1; i <= n; ++i) {
        if (viz[i] == 0) {
            ++rez;
            dfs(i);
        }
    }
    return rez;
}

int main() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        f >> x >> y;
        vecini[x].push_back(y);
    }
    f.close();
    g << compConexe();
    g.close();

    return 0;
}