Cod sursa(job #2212495)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 14 iunie 2018 12:08:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

vector <int> G[100005];

bool sel[100005];

int x, y;

int N, M;

void load ()
{
    f>>N>>M;

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

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

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()
{
    load();

    int nc=0;

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

    g<<nc<<'\n';
    return 0;
}