# PBinfo #1603 – ComponenteConexe3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("componenteconexe3.in");
ofstream fout("componenteconexe3.out");
int n , a[105][105];
int x[105], // coada pentru parcurgerea in latime
	v[105]; // vector caracteristic care precizeaza daca un varf a fost sau nu vizitat
int nrv[105], // numarul de varfuri din fiecare componenta conexa
	nrm[105]; // numarul de muchii din fiecare componenta conexa
void bf(int varf, int nrc)
{
	int st, dr;
	st = dr = 1;
	v[varf] = nrc;
	x[1] = varf;
	while(st <= dr)
	{
		int k = x[st];
		for(int i = 1; i <= n ; ++i)
			if(v[i] == 0 && a[k][i] == 1)
			{
				dr ++;
				v[i] = nrc;
				x[dr] = i;
			}
		st ++;
	}
}
int main()
{
    int i , j;
    fin >> n;
    while(fin >> i >> j)
    {
    	a[i][j] = a[j][i] = 1;
    }
	//determinam componentele conexe
    int nrc = 0;
    for(int i=1; i <= n ;++i)
		if(v[i] == 0 )
		{
			nrc ++;
			bf(i , nrc);
		}
	//determinam cate varfuri are fiecare componenta conexa
	for(int i = 1; i <= n ; i++)
		nrv[v[i]] ++;
	//determinam indexul componentei cu numar maxim de varfuri
    int CC = 1;
    for(int i = 2 ; i <= nrc ; i ++)
        if(nrv[i] > nrv[CC])
            CC = i;
    //determinareprezentanul componentei CC
    int repr = 0;
    for(int i = 1 ; i <= n && repr == 0; i ++)
        if(v[i] == CC)
            repr = i;
    fout << repr << " " << nrv[CC];
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1603)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1603/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1603/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)