Cod sursa(job #1723230)

Utilizator dominiciorgandaDominic Iorganda dominiciorganda Data 30 iunie 2016 03:30:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int>f[100001];
int k,i,m,x,j,ct;
bool g[100001];
void DFS(int x)
{
    int k,i,m;
    g[x]=1;
    for(k=0;k<f[x].size();k++)
    {
        if(!g[f[x][k]])
            DFS(f[x][k]);
    }
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%d%d",&i,&j);
        f[i].push_back(j);
        f[j].push_back(i);
    }
    for(k=1,i=0;k<=x;k++)
    {
        if(!g[k])
        {
            DFS(k);
            i++;
        }
    }
    printf("%d\n",i);
    return 0;
}