Cerinţa

Se dă lista muchiilor unui graf neorientat. Pentru fiecare componentă conexă numim cel mai mic vârf de ea reprezentant al componentei conexe.

Determinați reprezentantul componentei conexe cu cele mai multe vârfuri și câte noduri conține aceasta.

Date de intrare

Fişierul de intrare componenteconexe3.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire componenteconexe3.out va conţine pe prima linie reprezentantul componentei conexe cu număr maxim de noduri și numărul maxim de noduri, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta
• dacă sunt mai multe componente conexe cu număr maxim de vârfuri se va determina aceea cu reprezentantul minim

Exemplu

componenteconexe3.in

5
1 5 
3 5
2 4

componenteconexe3.out

1 3

#include <bits/stdc++.h>

using namespace std;

ifstream cin("componenteconexe3.in");
ofstream cout("componenteconexe3.out");

int n , x , y , C[101] , cnt , maxi , rez , f[101];
vector <int> G[101];

void dfs(int v , int c)
{
    C[v] = c;
    for(int i : G[v])
        if(!C[i]) dfs(i , c);

}


int main()
{
    cin >> n;
    while(cin >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1 ; i <= n ; i++)
        if(C[i] == 0) cnt++ , dfs(i , cnt);

    for(int i = 1 ; i <= n ; i++)
        f[C[i]]++;
    for(int i = 1 ; i <= n ; i++)
        if(f[i] > maxi) maxi = f[i] , rez = i;

    cout << rez << " " << maxi;
}