Cod sursa(job #1193560)

Utilizator ZenusTudor Costin Razvan Zenus Data 31 mai 2014 23:37:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 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];
bool sel[NMAX];

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

    sel[nod]=true;
    for (it=G[nod].begin();it!=G[nod].end();++it)
    {
        if (sel[*it]) continue;
        DFS(*it);
    }
}

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;
}