Cerința

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați numărul de vârfuri ale componentei tare conexe în care se află vârful k.

Date de intrare

Programul citește de la tastatură numărul n de noduri și numărul m de arce și numărul k, 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, reprezentând numărul de vârfuri ale componentei tare conexe în care se află vârful k.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 100

Exemplu

Intrare

8 12 3
1 3
3 5
5 7
7 1
2 6
6 8
8 2
1 4
4 6
4 8
4 2
1 8

Ieșire

4

Explicație

Graful are 3 componente tare conexe {1,3,5,7}, {2,6,8} și {4}, iar vârful 3 se află în componenta {1,3,5,7}.

#include <bits/stdc++.h>

using namespace std;

vector <int> G[101];
vector <int> H[101];

int n , m , x , y , k , S[101] , D[101] , c , cnt;

void dfs_succ(int nod , int val)
{
    S[nod] = val;
    for(auto p : G[nod])
        if(!S[p]) dfs_succ(p , val);
}

void dfs_pred(int nod , int val)
{
    D[nod] = val;
    for(auto p : H[nod])
        if(!D[p]) dfs_pred(p , val);
}

int main()
{
    cin >> n >> m >> k;
    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 j = 1 ; j <= n ; j++)
                if(S[j] != D[j]) S[j] = D[j] = 0;
        }

    for(int i = 1 ; i <= n ; i++)
        if(S[i] == S[k]) cnt++;
    cout << cnt;
}