Cod sursa(job #1507493)

Utilizator bogdanel32Bogdan bogdanel32 Data 21 octombrie 2015 18:13:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>

#include <algorithm>

#include  <vector>

using namespace std;

const int NMAX=100000;

vector <int> G[NMAX+5];

bool viz[NMAX+5];

void dfs(int u)
{
    int i;
    viz[u]=1;
    for(i=0;i<(int)G[u].size();++i)
        {
            int v=G[u][i];
            if(!viz[v]) dfs(v);
        }

}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n,m,i,u,v;
    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);
        }
    int cc=0;
    for(i=1;i<=n;++i)
        {
            if(!viz[i])
                    {
                    cc++;
                    dfs(i);
                    }
        }
    printf("%d",cc);
    return 0;
}