Cod sursa(job #1804036)

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

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

int N , M , e1 ,e2 , arr[10000][10000] , used[100000] , nr;

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

void solve (int x)
{
    int i;
    used[x] = 1;
    for(i = 1 ; i <= N ; ++ i)
    {
        if(arr[x][i] == 1 && used[i] == 0)
            solve (i);
    }
}

int main()
{
    read_input ();

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

    out << nr;
    return 0;
}