Cod sursa(job #3316883)

Utilizator Moti15Motirlichie Luca Andrei Moti15 Data 21 octombrie 2025 13:16:29
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n, m, nr;
vector<int>  L[10000001];
int viz[10000001];
void DFS(int nod) {
    viz[nod] = 1;
    for (auto vecin : L[nod]) {
        if (viz[vecin] == 0)
            DFS(vecin);
    }
}
int main() {
    ifstream fin("dfs.in");
    fin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        int nod;
        fin >> nod;
        L[i].push_back(nod);
    }
    for (int i = 1 ; i <= n ; i++) {
        if (viz[i] == 0){
            nr++;
            DFS(i);
        }
    }
    ofstream fout("dfs.out");
    fout << nr;
}

// #include <bits/stdc++.h>
// using namespace std;
//
// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//
//     int N, M;
//     if (!(cin >> N >> M)) return 0;
//
//     vector<vector<int>> adj(N + 1);
//     for (int i = 0; i < M; ++i) {
//         int x, y;
//         cin >> x >> y;
//         adj[x].push_back(y);
//         adj[y].push_back(x);
//     }
//
//     vector<char> visited(N + 1, 0);
//     int components = 0;
//
//     for (int i = 1; i <= N; ++i) {
//         if (visited[i]) continue;
//         ++components;
//         // iterative DFS using stack
//         stack<int> st;
//         st.push(i);
//         while (!st.empty()) {
//             int u = st.top(); st.pop();
//             if (visited[u]) continue;
//             visited[u] = 1;
//             for (int v : adj[u])
//                 if (!visited[v]) st.push(v);
//         }
//     }
//
//     cout << components << '\n';
//     return 0;
// }