Cod sursa(job #3266575)

Utilizator Edi17roAnghel Eduard Edi17ro Data 9 ianuarie 2025 16:08:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
//DFS ARHIVA ED INFOARENA
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int NMAX = 100000;
int n, m;
int u, v;
vector<int>g[NMAX + 1];
int cc;
bool viz[NMAX + 1];

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

int main()
{
    in >> n >> m;
    int i, j;
    for(i = 1; i <= m; ++i)
    {
        in >> u >> v;
        if(find(g[u].begin(), g[u].end(), v) == g[u].end())
        {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }


    for(i = 1; i <= n; ++i)
    {
        if(!viz[i])
        {
            ++cc;
            dfs(i);
        }
    }

    out << cc;
    return 0;
}