Cod sursa(job #2148188)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 1 martie 2018 16:24:11
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>
#define N 100002

using namespace std;

int n, m;
bool ok[N];
vector<int> A[N];

void dfs(int x)
{
    int i;
    for(i=0; i<A[x].size(); i++)
    {
        if(!ok[A[x][i]])
        {
            ok[A[x][i]]=1;
            dfs(A[x][i]);
        }
    }
}

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

    int i,j,cnt=0;

    scanf("%d %d ", &n, &m);

    while(m)
    {
        scanf("%d %d ", &i, &j);
        A[i].push_back(j);
        m--;
    }

    for(i=1; i<=n; i++)
    {
        if(!ok[i])
        {
            cnt++;
            ok[i]=1;
            dfs(i);
        }
    }

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

    return 0;
}