Cod sursa(job #1032707)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 15 noiembrie 2013 23:05:30
Problema Parcurgere DFS - componente conexe Scor 15
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();
}

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

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

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

    Citire();
    for (int i = 1; i <= N; ++i)
    {
        if (!B[i])
        {
            DFS(i);
            D++;
        }
    }
    Afisare();
    return 0;
}