Cod sursa(job #812882)

Utilizator monica11Szekely Monica monica11 Data 14 noiembrie 2012 17:19:45
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
#define BM 100005
typedef vector<int>::iterator it;
vector<int> g[BM];
int n,m,c;
bitset<BM>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 a,b,i;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;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);
    return 0;
}