Cod sursa(job #3300101)

Utilizator SimifilLavrente Simion Simifil Data 12 iunie 2025 20:57:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

const int maxn = 100002;
vector<int> adj[maxn];
bool vis[maxn];

void dfs( int parinte )
{
    for( auto copil : adj[parinte] )
    {
        if( vis[copil] == false )
        {
            vis[copil] = true;
            dfs( copil );
        }
    }
}

int main()
{
    int n, m;
    f >> n >> m;
    for( int i = 1; i <= n; ++i )
        vis[i] = false;
    for( int i = 1; i <= m; ++i )
    {
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int ans = 0;
    for( int i = 1; i <= n; ++i )
    {
        if( vis[i] == false )
        {
            vis[i] = true;
            ++ans;
            dfs(i);
        }
    }
    g << ans;
	return 0;
}