Cod sursa(job #560557)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 18 martie 2011 16:15:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<vector.h>
#include<queue.h>
#include<bitset>

#define dim 101000
#define pb push_back

using namespace std;
vector <int>v[dim];
bitset <dim> viz;
queue <int > q;
int n,m,x,y;
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1 ; i<=m;i++)
    {
        scanf("%d %d",&x ,&y);
        v[x].pb(y);
        v[y].pb(x);
    }
}
inline void dfs(int x )
{
    for(q.push(x) ; !q.empty(); q.pop())
    {
        x = q.front();
        for(int i=0 ; i<v[x].size(); i++)
        {
            if ( viz [v[x][i]] == 0)
            {
                q.push(v[x][i]);
                viz[v[x][i]] = 1 ;
            }
        }
    }
}
void solve()
{
    int nr =0;
    for(int i=1 ; i<=n;i++)
    {
        if ( viz[i]==0)
        {
            nr++;
            dfs(i);
        }
    }
    printf("%d ", nr );
}
int main ()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    read();
    solve();

    return 0;
}