Cod sursa(job #1832302)

Utilizator hegedusPaul Hegedus hegedus Data 19 decembrie 2016 19:17:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <vector>
#define nmax 100001
using namespace std;

int n,m,x,nr,i,j;
bool viz[nmax];
vector <int> a[nmax];

void citire()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(x=1;x<=m;x++)
    {
        scanf("%d%d",&i,&j);
        a[i].push_back(j);
        a[j].push_back(i);
    }
}

void dfs(int x)
{
    viz[x]=1;
    for(int y=0;y<a[x].size();y++)
        if(!viz[a[x][y]])
            dfs(a[x][y]);
}

int main()
{
    citire();
    for(x=1;x<=n;x++)
    {
        if(!viz[x])
            nr++,
            dfs(x);
    }
    printf("%d\n",nr);
    return 0;
}