Cod sursa(job #2785804)

Utilizator VladS23Vlad Seba VladS23 Data 19 octombrie 2021 16:08:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 1e5;

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

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

void read(int n, int m)
{
    edges.resize(n);
    viz.resize(n);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        edges[a - 1].push_back(b - 1);
        edges[b - 1].push_back(a - 1);
    }
}

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

void dfs(int node)
{
    viz[node] = 1;

    for (auto next : edges[node])
    {
        if (viz[next] == 0)
        {
            //cout << node + 1 << " -> " << next + 1 << '\n';
            dfs(next);
        }
    }
}

void bfs(int node)
{
    queue<int> q;
    q.push(node);

    viz[node] = 1;

    while (!q.empty())
    {
        node = q.front();
        q.pop();

        for (auto next : edges[node])
        {
            if (viz[next] == 0)
            {
                q.push(next);
                viz[next] = 1;
                //cout << node + 1 << " -> " << next + 1 << '\n';
            }
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    read(n, m);

    int sol = 0;
    for (int i = 0; i < edges.size(); i++)
    {
        if (viz[i] == 0)
        {
            sol++;
            dfs(i);
        }
    }

    cout << sol;
    return 0;
}