Cod sursa(job #2230836)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 11 august 2018 19:28:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 100005;
vector<int>L[NMAX];
bool viz[NMAX];
int cnt = 0;

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

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n , m;
    scanf("%d%d",&n,&m);
    int u , v;
    for(int i = 1 ; i <= m ; i++)
    {
        scanf("%d%d",&u,&v);
        L[u].push_back(v);
        L[v].push_back(u);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(!viz[i])
        {
            cnt++;
            dfs(i);
        }
    }
    printf("%d",cnt);
    return 0;
}