Cod sursa(job #842143)

Utilizator monica11Szekely Monica monica11 Data 26 decembrie 2012 12:51:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
#define dim 100005
using namespace std;
typedef vector<int>::iterator it;
vector<int>g[dim];
int n,m,c;
bitset <dim> viz;
void dfs(int i)
{
    for(it ii=g[i].begin();ii!=g[i].end();++ii)
    if(!viz[*ii])
    {
        viz[*ii]=1;
        dfs(*ii);
    }
}
int main ()
{
    int i,a,b;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(i=1;i<=n;++i)
    if(!viz[i])
    {
        c++;
        dfs(i);
    }
    printf("%d",c);
}