Cod sursa(job #1654607)

Utilizator DanBrezeanuBrezeanu Dan DanBrezeanu Data 17 martie 2016 11:57:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 1e5;

bool viz[NMAX];
vector<int>G[NMAX];

int n,m;

void dfs(int u)
{
    viz[u] = 1;

    for(size_t i=0;i<G[u].size();++i)
        if(!viz[G[u][i]])
            dfs(G[u][i]);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    int pos1,pos2,cc=0;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&pos1,&pos2);

        G[pos1].push_back(pos2);
        G[pos2].push_back(pos1);
    }

    for(int i=1;i<=n;++i)
        if(!viz[i])
        {
            cc++;
            dfs(i);
        }

        printf("%d\n",cc);
}