Cod sursa(job #1193562)

Utilizator ZenusTudor Costin Razvan Zenus Data 31 mai 2014 23:38:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

#define NMAX 100003

int N,M,i,X,Y,componente;
vector < int > G[NMAX];
queue <int> Q;
bool sel[NMAX];

void DFS(int nod)
{
    vector < int > :: iterator it;

    Q.push(nod);
    sel[nod]=true;

    while (!Q.empty())
    {
        for (it=G[Q.front()].begin();it!=G[Q.front()].end();++it)
        {
            if (sel[*it]) continue;
            sel[*it]=true;
            Q.push(*it);
        }

        Q.pop();
    }
}

int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);

scanf("%d%d",&N,&M);

for (i=1;i<=M;++i)
{
    scanf("%d%d",&X,&Y);
    G[X].push_back(Y);
    G[Y].push_back(X);
}

for (i=1;i<=N;++i)
{
    if (sel[i]) continue;
    ++componente;
    DFS(i);
}

printf("%d\n",componente);

return 0;
}