Cod sursa(job #3243618)

Utilizator seby1337Goran Sebastian-Alexandru seby1337 Data 19 septembrie 2024 19:19:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const string file = "dfs";
ifstream fin(file+".in");
ofstream fout(file+".out");

const int dim = 1e5+1;
int n, m, i, cm[dim];
vector<int> g[dim];

void dfs(int nod, int prev, int nr)
{
    cm[nod] = nr;
    for (auto x : g[nod])
    {
        if (x == prev || cm[x])
            continue;
        dfs(x, nod, nr);
    }
}

int main()
{
    fin >> n >> m;
    int x, y;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    int cnt = 0;
    for (i = 1; i <= n; i++)
    {
        if (!cm[i])
        {
            cnt++;
            dfs(i, i, cnt);
        }
    }
    fout << cnt;
    return 0;
}