Cod sursa(job #2451475)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 26 august 2019 21:01:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graph(100001, vector<int>());
int N, M, answer;

void read_from_file(string const& file_path)
{
    ifstream fin{file_path};
    fin >> N >> M;

    int x, y;

    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y;
        graph.at(x).push_back(y);
        graph.at(y).push_back(x);
    }
}

void print_to_file(string const& file_path)
{
    ofstream fout{file_path};

    fout << answer;
}

void dfs(int node, vector<bool>& visited)
{
    visited.at(node) = true;
    for(auto& elem : graph.at(node))
    {
        if(visited.at(elem) == false) dfs(elem, visited);
    }
}

void solve()
{
    answer = 0;
    vector<bool> visited(100001, false);

    for(int i = 1; i <= N; i++)
    {
        if(visited.at(i) == false)
        {
            answer++;
            dfs(i, visited);
        }
    }
}
int main()
{
    read_from_file("dfs.in");

    solve();

    print_to_file("dfs.out");
}