# PBinfo #1917 – Catalin si prietenii – Rezolvare C++

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

## Enunț

Cerința
Cătălin avea un singur prieten dar, fiind foarte sociabil, el se împrietenește automat cu toți prietenii prietenului său și cu prietenii prietenilor acestuia ș.a.m.d. (s-a inspirat din modelul Facebook).

Inițial, în grupul de persoane, nimeni nu are prieteni dar, pe parcursul timpului, se leagă noi relații de prietenie.

Definim două tipuri de operații:


1 x y  – ce reprezintă faptul că x se împrietenește cu y.
2 p – Cătălin vă întreabă care este numărul de prieteni pe care îi poate avea, dacă inițial ar fi prieten doar cu p. Se va ține cont doar de relațiile de prietenie stabilite până în acel moment.

Date de intrare
Fișierul de intrare prieteni.in conține pe prima linie numerele N K, unde N este numărul de persoane, iar K este numărul de operații. Următoarele K linii conțin câte o operație din unul dintre tipurile de mai sus.

Date de ieșire
În fişierul de ieşire prieteni.out se găsesc răspunsurile doar la operațiile de tip 2, în ordinea în care apar în fişierul de intrare. Pe fiecare linie i va fi scris un număr, reprezentând răspunsul la a i-a întrebarea de tip 2 citită.

Restricții și precizări

1 < N < 1.000.000
1 < K < 1.000.000
Relația de prietenie este reciprocă.

Exemplu:
prieteni.in

10 10
1 6 7
1 4 5
1 10 8
2 2
1 4 8
2 9
2 4
1 8 3
2 10
2 9
prieteni.out

1
1
4
5
1
Explicație

1 = numărul de prieteni pe care îi va avea dacă se împrietenește cu 2 la întrebarea 2 2
1 = numărul de prieteni pe care îi va avea dacă se împrietenește cu 9 la întrebarea 2 9
4 = numărul de prieteni pe care îi va avea dacă se împrietenește cu 4 care s-a împrietenit anterior cu 5 şi 8, 8 fiind deja prieten cu 10
ș.a.m.d.

## Cod sursă C++

```cpp
// sursa 100p Turcuman Vlad
#include <fstream>
#define NMax 100001
using namespace std;
ifstream fin("prieteni.in");
ofstream fout("prieteni.out");
int c[NMax];
int p[NMax];
int n,k,t,x,y;
int _find(int x)
{
    return !p[x] ? x : (p[x] = _find(p[x]));
}
void Union(int x,int y)
{
    int p1 = _find(x);
    int p2 = _find(y);
    if(p1==p2)
        return;
    p[p1] = p2;
    c[p2] += c[p1] + 1;
}
int Children(int x)
{
    return c[_find(x)];
}
int main()
{
    fin>>n>>k;
    if(k>1000000)
        return 0;
    for(int i =1;i<=k;i++)
    {
        fin>>t;
        if(t == 1)
        {
            fin>>x>>y;
            Union(x,y);
        }
        else
        {
            fin>>x;
            fout<<Children(x) + 1<<'\n';
        }
    }
    return 0;
}
```

## Resurse

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