Cod sursa(job #1032700)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 15 noiembrie 2013 22:57:36
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <vector>
#include <memory.h>

#define Nmax 100001

using namespace std;

vector <int> A[Nmax];
int N, M, B[Nmax], C[Nmax], D;

void Citire()
{
    int n1, n2;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d%d", &n1, &n2);
        A[n1].push_back(n2);
    }
    for (int i = 1; i <= N; ++i)
        C[i] = A[i].size();
    memset(B, -1, sizeof(B));
    B[1] = 1;
}

void DFS(int nod)
{
    D++;
    for (int i = 0; i < C[nod]; ++i)
    {
        if (B[A[nod][i]] == -1)
        {
            B[A[nod][i]] = 1;
            DFS(A[nod][i]);
        }
    }
}

void Afisare()
{
    printf("%d", D);
}

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

    Citire();
    DFS(1);
    Afisare();
    return 0;
}