Cod sursa(job #2258833)

Utilizator hristacheruxiRuxandra Hristache hristacheruxi Data 12 octombrie 2018 11:33:22
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 100000
vector <int>v[N];
int seen[N];
int n, m;

void citire(int &n, int &m)
{
    int a, b;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        v[a - 1].push_back(b - 1);
    }

}

void DFS(int nod)
{
    seen[nod] = -1;
    for (int i = 0; i < v[nod].size(); i++)
        if (seen[v[nod][i]] == 0)
            DFS(v[nod][i]);
}

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

    citire(n, m);

    for (i = 0; i < n; i++)
    {
        if (seen[i] == 0)
        {
            cate++;
            DFS(i);
        }
    }

    printf("%d", cate);
    return 0;
}