Cod sursa(job #830532)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 7 decembrie 2012 00:31:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
#include<bitset>
using namespace std;
vector<int> v[100001];
bitset<100001> p;
int n,m,a,b,cnt;
void dfs(int x)
{
    int i,q;
    if(p[x]) return;
    q=v[x].size();
    p[x]=1;
    for(i=0;i<q;i++)
    {
        dfs(v[x][i]);
    }
}
int main()
{
    int i;
    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);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
    {
        if(!p[i]) {cnt++; dfs(i);}
    }
    printf("%d\n",cnt);
    return 0;
}