Cod sursa(job #2085801)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 10 decembrie 2017 18:41:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
#define MN 100005
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int N, M, nr;
bitset <MN> viz;
typedef struct _nod
{
    int vf;
    _nod* next;
} *pnod;
pnod G[MN];

void add(int a, int b)
{
    pnod p = new _nod;
    p->vf = b;
    p->next = G[a];
    G[a] = p;
}

void dfs(int nod)
{
    viz.set(nod);
    for(pnod p = G[nod]; p; p = p->next)
        if(!viz.test(p->vf))
            dfs(p->vf);
}

int main()
{
    in >> N >> M;
    for(int a, b; M; M--)
    {
        in >> a >> b;
        add(a, b);
        add(b, a);
    }
    for(int i = 1; i <= N; ++i)
        if(!viz.test(i))
            dfs(i), nr++;
    out << nr << '\n';
    in.close(), out.close();
    return 0;
}