Cod sursa(job #2500745)

Utilizator nicu_ducalNicu Ducal nicu_ducal Data 28 noiembrie 2019 16:53:31
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
typedef unsigned int ui;
typedef long long ll;
using namespace std;

int N, M;
bool viz[1000010];

vector <int> V[1000010];

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

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

    cin >> N >> M;

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

    int num = 0;
    for (int i = 1; i <= N; i++)
    {
        if (!viz[i])
        {
            dfs(i);
            num++;
        }
    }


    cout << num;


    return 0;
}