Cod sursa(job #3004794)

Utilizator bogdan_zamfiroiuZamfiroiu Bogdan Marian bogdan_zamfiroiu Data 16 martie 2023 16:48:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>

using namespace std;

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

int viz[100001], k, n, m, a, b;
vector <int> V[100001];

void DFS(int v)
{
    viz[v] = 1;
    for (int i = 0; i < V[v].size(); i++)
        if (!viz[V[v][i]])
        {
            DFS(V[v][i]);
        }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!viz[i]) k++;
        DFS(i);
    }
    cout << k;
    return 0;
}