Cod sursa(job #2275547)

Utilizator anamaria41Raicu Ana anamaria41 Data 3 noiembrie 2018 11:54:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <vector>
using namespace std;

bool sel[100050];
int n,m,x,y,nc;
vector <int> G[100050];

void df(int x)
{
    int i;
    sel[x]=true;
    for (i=0; i<G[x].size(); i++ )
        if (!sel[G[x][i]])
            df(G[x][i]);
}


int main()
{
    freopen ("dfs.in", "r", stdin);
    freopen ("dfs.out", "w", stdout);

    scanf ("%d%d", &n, &m);

    for (int i=1; i<=m; i++ )
    {
        scanf ("%d%d", &x,&y);
       G[x].push_back(y);
       G[y].push_back(x);

    }

    nc=0;

    for (int i=1;i<=n;i++)
        if (!sel[i] )
    {
        nc++;
        df(i);
    }

    printf ("%d\n", nc);

    return 0;
}