Cod sursa(job #1980216)

Utilizator IoanZioan zahiu IoanZ Data 12 mai 2017 16:15:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector <int>G[100005];
bool viz[100005];


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

int main()
{
    freopen ( "dfs.in", "r", stdin );
    freopen ( "dfs.out", "w", stdout );
    int n, i, m, nr, u, v;
    scanf ( "%d%d", &n, &m );
    for ( i = 1; i <= m; i++ )
    {
        scanf ( "%d%d", &u, &v );
        G[u].push_back ( v );
        G[v].push_back ( u );
    }
    nr = 0;
    for ( i = 1; i <= n; i++ )
    {
        if ( !viz[i] )
        {
            nr++;
            dfs ( i );
        }
    }
    printf ( "%d", nr );
    return 0;
}