Cod sursa(job #2714673)

Utilizator EusebiudistrugatorulLionel Messi Eusebiudistrugatorul Data 2 martie 2021 11:09:58
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> cnt(100001), nodes[100001];
vector<bool> visited(100001, false);
unordered_set<int> my_set;

void DFS(int node) {
    for (int i = 0; i < nodes[node].size(); ++i) {
        if (!visited[nodes[node][i]]) {
            visited[nodes[node][i]] = true;
            cnt[nodes[node][i]] = cnt[node];
            DFS(nodes[node][i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    fin >> n >> m;
    while (m--) {
        int node_1, node_2;
        fin >> node_1 >> node_2;
        nodes[node_1].push_back(node_2);
    }
    iota(cnt.begin(), cnt.end(), 0);
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            DFS(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        my_set.insert(cnt[i]);
    }
    fout << my_set.size();
    return 0;
}