Cerința

Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe are graful dat.

Date de intrare

Programul citește de la tastatură numărul n de noduri și numărul m de arce, iar apoi lista arcelor, formată din m perechi de forma i j, cu semnificația că există arc orientat de la nodul i la nodul j.

Date de ieșire

Programul va afișa pe ecran numărul C de componente tare conexe.

Restricții și precizări

• 1 ≤ n ≤ 100

Exemplu

Intrare

5 7
1 2
2 1
2 4
4 1
3 5
4 5
5 3

Ieșire

2

Explicație

Cele două componente tare conexe sunt: 1 2 4 și 3 5

#include <bits/stdc++.h>

using namespace std;

vector <int> G[100002];
vector <int> H[100002];
int n , m , x , y , S[100001] , D[100001] , c;

void dfs_succ(int v , int c)
{
    S[v] = c;
    for(int i : G[v])
        if(!S[i]) dfs_succ(i , c);
}

void dfs_pred(int v , int c)
{
    D[v] = c;
    for(int i : H[v])
        if(!D[i]) dfs_pred(i , c);
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        H[y].push_back(x);
    }

    for(int i = 1 ; i <= n ; i++)
        if(!S[i])
        {
            c++;
            dfs_succ(i , c);
            dfs_pred(i , c);
            for(int i = 1 ; i <= n ; i++)
                if(S[i] != D[i]) S[i] = D[i] = 0;
        }

    cout << c;

}