Cod sursa(job #3249571)

Utilizator Tudi2604Tudor-Dimitrie Iordache Tudi2604 Data 17 octombrie 2024 01:51:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>

std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");

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

    for (auto it : adj[s])
        if (visited[it] == false)
            DFSRec(adj, visited, it);
}

void DFS(std::vector<std::vector<int>> &ad, int start)
{
    int comp = 0;
    std::vector<bool> visited(ad.size(), false);
    for (int i = 1; i < ad.size(); i++)
    {
        if (visited[i] == false)
        {
            DFSRec(ad, visited, i);
            comp += 1;
        }
    };
    fout << comp;
}

void addEdge(std::vector<std::vector<int>> &ad, int u, int v)
{
    ad[u].push_back(v);
    ad[v].push_back(u);
}

int main()
{
    int muchii, noduri, v, u;
    fin >> noduri >> muchii;
    std::vector<std::vector<int>> ad(noduri + 1);

    for (int i = 0; i < muchii; i++)
    {
        fin >> u >> v;
        addEdge(ad, u, v);
    }
    DFS(ad, 1);
    return 0;
}