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

prieteni.out

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Catalin si prietenii:

// 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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1917 Catalin si prietenii

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1917 Catalin si prietenii de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1917 Catalin si prietenii