Cod sursa(job #1804073)

Utilizator LazarAndreiLazar Andrei Teodor LazarAndrei Data 12 noiembrie 2016 10:49:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;

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

vector <int> L[100003];
int N , M , e1 ,e2 , nr , used[100003] , v[100003];

void read_input ()
{
    in >> N >> M;
    for(int i = 1 ; i <= M ; ++ i)
    {
        in >> e1 >> e2;
        v[e1] ++ ;
        v[e2] ++ ;
        L[e1].push_back(e2);
        L[e2].push_back(e1);
    }
}

void solve (int x)
{
    used[x] = 1;

    for(int i = 0 ; i < v[x] ; ++ i)
    {
        if(!used[L[x][i]])
            solve(L[x][i]);
    }

}


int main()
{
    read_input ();

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

    out << nr;
    return 0;
}