Cod sursa(job #2777198)

Utilizator andcovAndrei Covaci andcov Data 22 septembrie 2021 16:15:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
//
// Created by Andrei Covaci on 03.09.2021.
//

#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
//#define INPUT "input.in"
//#define OUTPUT "output.out"

using namespace std;

vector<vector<int>> read() {
    ifstream in(INPUT);

    int n, m, tail, head;
    in >> n >> m;

    vector<vector<int> > list;
    list.reserve(n);
    for(int i = 0; i < n; ++i) {
        list.emplace_back();
    }

    for(int i = 0; i < m; ++i) {
        in >> tail >> head;
        tail--;
        head--;
        list[tail].push_back(head);
        list[head].push_back(tail);
    }

    in.close();
    return list;
}



int solve(vector<vector<int>>& list) {
    vector<bool> visited;
    visited.reserve(list.size());
    for(int i = 0; i < list.size(); ++i) {
        visited.push_back(false);
    }

    int cnt = 0;

    for(int i = 0; i < list.size(); ++i) {
        if (!visited[i]) {
            cnt++;
            stack<int> s;
            s.push(i);

            while(!s.empty()) {
                int curr = s.top();
                s.pop();

                for(auto e : list[curr]) {
                    if(!visited[e]) {
                        s.push(e);
                        visited[e] = true;
                    }
                }
            }
        }
    }

    return cnt;
}

void print(int c) {
    ofstream out(OUTPUT);

    out << c;

    out.close();
}

int main() {
    auto nums = read();
    auto res = solve(nums);
    print(res);

    return 0;
}