Cod sursa(job #698942)

Utilizator mihaitza22Mihai Nan mihaitza22 Data 29 februarie 2012 16:52:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <vector>

#define Nmax 100001
#define pb push_back

using namespace std;

int n, m, i, j, x, y, nr, viz[Nmax];
vector <int> G[Nmax];

int dfs(int nod)
{
    int i;
    if(viz[nod])
        return 0;
    viz[nod]=nr;
    for(i=0;i<G[nod].size();i++)
        dfs(G[nod][i]);
    return 0;
}

void citire()
{
    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].pb(y);
        G[y].pb(x);
    }
}

void parcurgere()
{
    for (int i = 1;i<=n;i++)
        if (viz[i]==0)
        {
            nr++;
            dfs(i);
        }
}

int main()
{
    citire();
    parcurgere();
    printf("%d ", nr);
    return 0;

}