Cod sursa(job #1003671)

Utilizator valiro21Valentin Rosca valiro21 Data 1 octombrie 2013 11:31:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

//defines
#define NMax 100001
#define For(i,a,b) for(long i=a;i<=b;i++)
#define scan scanf

//stl defines
#define V vector<long>
#define Q queue<long>
#define IFor(i,a) for(V::iterator i=a.begin();i<a.end();i++)
#define pb push_back
#define pf pop_front
#define viz(a) viz[a]=1

//variables
V v[NMax];
long n,m,x,y,count;
bool viz[NMax];

//breadth-first search(BFS)
void bfs(long now) {
    Q q;
    q.push(now);viz(now);
    while(!q.empty()) {
        now=q.front();  //get next element in q

        IFor(i,v[now])  //for each connected vertex
            if(!viz[*i])
                q.push(*i),  //add element to q
                viz(*i);

        q.pop(); //remove front(current) element in q
    }
}

//deep-first search
void dfs(long now) {
    viz(now);
    IFor(i,v[now])  //for each connected vertex
        if(!viz[*i])
            dfs(*i);
}

//main
int main()
{
    freopen("dfs.in","rt",stdin);
    freopen("dfs.out","wt",stdout);

    scan("%ld %ld",&n,&m);
    For(i,1,m)
        scan("%ld %ld",&x,&y),
        v[x].pb(y),
        v[y].pb(x);

    For(i,1,n)
        if(!viz[i])
            dfs(i),count++;

    printf("%ld\n",count);

    return 0;
}