Cod sursa(job #1086811)

Utilizator gabrielvGabriel Vanca gabrielv Data 18 ianuarie 2014 16:13:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 100005

int N,M,Sol;
bool used[NMAX];

vector < int > G[NMAX];

void Read()
{
    freopen("dfs.in","r",stdin);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS(int nod)
{
    used[nod] = true;

    for(unsigned j=0;j<G[nod].size();j++)
        if(!used[G[nod][j]])
            DFS(G[nod][j]);
}

int main()
{
    Read();

    for(int i=1;i<=N;i++)
        if(!used[i])
        {
            Sol++;
            DFS(i);
        }

    freopen("dfs.out","w", stdout);

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

    return 0;
}