Cod sursa(job #1919168)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 9 martie 2017 18:13:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>

#define pb push_back

using namespace std;

const int NMax = 100005;
const int MMax = 200005;

int N, M;

vector < int > G[MMax];
bitset < NMax > viz;

void Read()
{
    scanf("%d %d", &N, &M);

    for(int i=1; i<=M; ++i)
    {
        int x, y;

        scanf("%d %d", &x, &y);

        G[x].pb(y);
        G[y].pb(x);
    }
}

void DFS(int x)
{
    viz[x] = 1;

    vector < int > ::iterator it;

    for(it=G[x].begin(); it!=G[x].end(); ++it)
    {
        if(!viz[*it])
            DFS(*it);
    }
}

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

    Read();

    int nr=0;

    for(int i=1; i<=N; ++i)
        if(!viz[i])
        {
            DFS(i);
            ++nr;
        }

    printf("%d", nr);

    return 0;
}