Cod sursa(job #1980192)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 12 mai 2017 15:52:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> g[100005];
int viz[100005];
void dfs(int nod)
{
    int i;
    viz[nod] = 1;
    for(i = 0 ; i < g[nod].size() ; i ++)
        if(!viz[g[nod][i]])
           dfs(g[nod][i]);
}
int main()
{
    freopen("dfs.in" , "r" , stdin);
    freopen("dfs.out" , "w" , stdout);
    int n , m , u , v , i , nr;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= m ; i ++)
    {
        scanf("%d%d" , &u , &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    nr = 0;
    for(i = 1 ; i <= n ; i ++)
         if(viz[i] == 0)
         {
             dfs(i);
             nr ++;
         }
    printf("%d\n" , nr);
    return 0;
}