Cod sursa(job #2831427)

Utilizator Artick5Andrei Artick5 Data 11 ianuarie 2022 13:07:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

bool visited[100000];

void dfs(int i, bool* visited, std::vector<std::vector<int>> &adj)
{
    visited[i] = true;

    for (int u : adj[i])
    {
        if (!visited[u])
        {
            dfs(u, visited, adj);
        }
    }
}

int solve(std::vector<std::vector<int>> &adj)
{
    int count = 0;

    for (int i = 1; i < adj.size(); i++)
    {
        if (!visited[i])
        {
            dfs(i, visited, adj);
            count = count + 1;
        }
    }

    return count;
}

int main()
{
    std::ifstream in;
    in.open("dfs.in");

    int n, m;
    in >> n;
    in >> m;

    std::vector<std::vector<int>> adj(n + 1);

    for (int i = 1; i <= m; i++)
    {
        int n1, n2;
        in >> n1;
        in >> n2;

        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
    }

    in.close();

    /*
    for (int i = 1; i <= n; i++)
    {
        std::cout << i << " ";
        for (int v : graph[i])
        {
            std::cout << v << " ";
        }

        std::cout << std::endl;
    }
    */

    std::ofstream of;
    of.open("dfs.out");

    of << solve(adj) << std::endl;
}