Cod sursa(job #719810)

Utilizator algotrollNume Fals algotroll Data 22 martie 2012 09:12:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
#include<vector>
#include<queue>
#define _NM 100010
using namespace std;
vector<int> lAd[_NM];

bool viz[_NM];
bool comp_conexa(int s)
{
    if (viz[s]) return 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int cur=q.front();q.pop();
        viz[cur]=1;
        for (vector<int>::iterator it=lAd[cur].begin();it!=lAd[cur].end();++it)
            if (!viz[*it]) q.push(*it);
    }
    return 1;
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int nN,nM;
    scanf("%d%d",&nN,&nM);
    for (int i=1;i<=nM;i++)
    {
        int nod1, nod2;
        scanf("%d%d",&nod1,&nod2);
        lAd[nod1].push_back(nod2);
        lAd[nod2].push_back(nod1);
    }
    int nr_con=0;
    for (int i=1;i<=nN;i++)
        if (comp_conexa(i)) nr_con++;
    printf("%d",nr_con);
    return 0;
}