Cerința

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor. Afișați componentele tare conexe formate din număr maxim de vârfuri.

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 de la nodul i la nodul j.

Date de ieșire

Programul va afișa pe ecran în ordine crescătoare și separate printr-un spațiu vârfurile din care este compusă componenta tare cu număr maxim de vârfuri. Dacă există mai multe componente tare conexe cu număr maxim de vârfuri, atunci se vor afișa pe linii separate. Ordinea acestora va fi crescătoare și dată de cel mai mic vârf din fiecare componentă.

Restricții și precizări

• 1 ≤ n ≤ 100

Exemplu

Intrare

14 19
1 3
3 5
5 7
7 1
2 6
6 8
8 2
1 4
4 6
4 8
4 2
1 8
2 9
9 6
10 11
11 12
12 13
13 10
10 13

Ieșire

1 3 5 7
2 6 8 9
10 11 12 13

Explicație

Graful are 5 componente tare conexe: {1,3,5,7}, {2,6,8,9}, {4}, {10,11,12,13} și {14}.

#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 , maxi , f[101];

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;
    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++)
        f[S[i]]++;
    for(int i = 1 ; i <= n ; i++)
        if(f[i] > maxi) maxi = f[i];

    for(int i = 1 ; i <= n ; i++)
        if(f[i] == maxi)
        {
            for(int j = 1 ; j <= n ; j++)
                if(S[j] == i) cout << j << " ";
            cout << '\n';
        }
}