Cod sursa(job #1556729)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 25 decembrie 2015 19:12:49
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <cstdio>
using namespace std;

const int dmax = 1000;

bool A[dmax+1][dmax+1];

int N,M;

bool viz[dmax+1];
int NR;

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

    //printf("%d ", nod);

    for(int i = 1; i <= N; i++)
        if(viz[i] == false && A[nod][i] == true) DFS(i);
}

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

    int i, x, y;

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

    for(i = 1; i <= M; i++)
    {
        scanf("%d %d", &x, &y);

        A[x][y] = A[y][x] = true;
    }

    for(i = 1; i <= N; i++)
        if(viz[i] == false)
        {
            NR++;
            DFS(i);
            //printf("\n");
        }

    printf("%d", NR);

    return 0;
}