Cod sursa(job #2785794)

Utilizator livliviLivia Magureanu livlivi Data 19 octombrie 2021 15:41:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.24 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("dfs.in");
ofstream cout ("dfs.out");

const int kNMax = 1000;

/************************** Matrice de adiacenta ********************/

// int n;
// bool edges[kNMax][kNMax];  // false

// void readGraph() {
//     cin >> n;  // numarul de noduri
//     int m; cin >> m;  // numarul de muchii
    
//     for (int i = 0; i < m; i++) {
//         int a, b; cin >> a >> b;  // capetele muchiei
//         a--; b--;
//         edges[a][b] = edges[b][a] = true;
//     }
// }

// void printGraph() {
//     cout << "  ";
//     for (int i = 0; i < n; i++) {
//         cout << i + 1 << " ";
//     }
//     cout << "\n";
    
//     for (int i = 0; i < n; i++) {
//         cout << i + 1 << " ";
//         for (int j = 0; j < n; j++) {
//             cout << edges[i][j] << " ";
//         }
//         cout << '\n';
//     }
//     cout << '\n';
// }

/************************** Liste de adiacenta *********************/

// int n;
// int edges[kNMax][kNMax];
// int grad[kNMax];

// void readGraph() {
//     cin >> n;  // numarul de noduri
//     int m; cin >> m;  // numarul de muchii

//     for (int i = 0; i < m; i++) {
//         int a, b; cin >> a >> b;  // capetele muchiei
//         a--; b--;
        
//         edges[a][grad[a]] = b;
//         grad[a]++;
        
//         edges[b][grad[b]] = a;
//         grad[b]++;
//     }
// }

// void printGraph() {
//     for (int i = 0; i < n; i++) {
//         cout << i + 1 << ": ";
//         for (int j = 0; j < grad[i]; j++) {
//             cout << edges[i][j] + 1 << " ";
//         }
//         cout << "\n";
//     }
//     cout << "\n";
// }

/*********************** Vectori (stl) de adiacenta *********************/

vector<vector<int>> edges;
vector<bool> viz;

void readGraph() {
    int n; cin >> n;  // numarul de noduri
    int m; cin >> m;  // numarul de muchii
    
    edges.resize(n);
    viz.resize(n);

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;  // capetele muchiei
        a--; b--;
        
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
}

void printGraph() {
    // for (auto node : edges) {
    //     for (auto next : node) {
    //         cout << node << " " << next << "\n";
    //     }
    // }
    
    for (int i = 0; i < edges.size(); i++) {
        cout << i + 1 << ": ";
        for (int j = 0; j < edges[i].size(); j++) {
            cout << edges[i][j] + 1 << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

// dfs(root)

void dfs(int node) {
    // Var 1
    // if (viz[node]) { return; }
    
    viz[node] = true;
    
    // for (int i = 0; i < edges[node].size(); i++) {
    //     int next = edges[node][i];
    for (auto next : edges[node]) {
        // Var 2
        if (viz[next] == false) {
            // cout << node + 1 << " -> " << next + 1 << "\n";
            dfs(next);
        }
    }
}

int main() {
    readGraph();
    // printGraph();
    // dfs(0);
    
    // n = edges.size();
    int count_con = 0;
    for (int i = 0; i < edges.size(); i++) {
        if (viz[i] == false) {
            count_con++;
            // cout << count_con << ":\n";
            dfs(i);
            // cout << "\n";
        }
    }
    
    cout << count_con << '\n';
    return 0;
}