Cod sursa(job #1717689)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 15 iunie 2016 16:09:26
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

int n, m;
vector<int> vecini[100100];
bitset<100100> viz;

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2;

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &tmp1, &tmp2);
        tmp1--;
        tmp2--;

        vecini[tmp1].push_back(tmp2);
        vecini[tmp2].push_back(tmp1);
    }
}

void dfs(int x)
{
    viz[x] = true;

    for(vector<int>::iterator it = vecini[x].begin(); it != vecini[x].end(); it++)
    {
        if(viz[*it] == false)
        {
            viz[*it] = true;
            dfs(*it);
        }
    }
}

bool isNotSeen()
{
    for(int i = 0; i < n; i++)
    {
        if(viz[i] == false)
        {
            dfs(i);
            return true;
        }
    }

    return false;
}

void solve()
{
    int nr = 0;

    while(isNotSeen() == true)
    {
        nr++;
    }

    printf("%d", nr);
}

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

    citire();
    solve();

    return 0;
}