La cursul de comunicare organizat în vacanță, au participat N persoane, numerotate cu numere de ordine de la 1 la N. Fiecare persoană are la curs mai mulți prieteni apropiați, cărora le comunică orice informație imediat cum a aflat-o. Relaţiile de comunicare nu sunt bidirecţionale, cu alte cuvinte dacă persoana a îi transmite imediat informații persoanei b, nu este obligatoriu ca şi persoana b să transmită imediat informaţiile pe care le primeşte persoanei a.

Profesorul studiază relaţiile dintre participanţii la curs. El defineşte un nucleu de comunicare ca fiind un grup cu număr maxim de cursanţi cu proprietatea că oricare ar fi a şi b doi cursanţi din grup, dacă a primeşte o informaţie, aceasta va ajunge şi la cursantul b (direct sau prin intermediul altor cursanţi din grup).

Profesorul dorește să determine numărul de nuclee de comunicare existente la cursul său.

Cerința

Cunoscând N, numărul de cursanţi, precum și prietenii fiecărui cursant, scrieţi un program care să determine numărul de nuclee de comunicare existente.

Date de intrare

Fișierul de intrare nuclee.in conține pe prima linie un număr natural N, reprezentând numărul de cursanţi. Următoarele N linii conțin informații despre prietenii cursanţilor. Astfel, pe linia i+1 din fişier se află numerele naturale k p[1] p[2] … p[k], separate prin câte un spaţiu, unde k reprezintă numărul de prieteni ai persoanei i, iar p[1] p[2] … p[k], reprezintă prietenii persoanei i.

Date de ieșire

Fișierul de ieșire nuclee.out va conține o singură linie pe care va fi scris un singur număr natural reprezentând numărul de nuclee de comunicare existente.

Restricții și precizări

1 < N < 201
Pot exista persoane care nu au prieteni apropiați.
O persoană poate face parte dintr-un singur nucleu.
Un nucleu poate fi format dintr-o singură persoană.

Exemplu

nuclee.in

nuclee.out

Explicație

Persoana 1 are 2 prieteni apropiaţi (3 şi 4)
Persoana 2 are de asemenea 2 prieteni apropiaţi (1 şi 3)
Persoana 3 are un prieten (pe 2)
Persoana 4 nu are prieteni.
Persoana 5 are doi prieteni (pe 1 şi pe 4).

Există 3 nuclee de comunicare.

N1: 1, 2, 3
N2: 4
N3: 5

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 Nuclee:

#include <fstream>
#include<cstdlib>
using namespace std;
ifstream fin("nuclee.in");
ofstream fout("nuclee.out");
int n,i, a[201][201],at[201][201],viz[201],post[201],nrc,nr;
void citire()
{
    int i,j,k,x;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>k;
        a[i][0]=k;
        for(j=1;j<=k;j++)
        {
            fin>>x;
            a[i][j]=x;
            at[x][0]++;
            at[x][at[x][0]]=i;
        }

    }
}
void dfs(int i)
{
    int j;
    viz[i]=1;
    for(j=1;j<=a[i][0];j++)
        if(!viz[a[i][j]])
            dfs(a[i][j]);
    post[++nr]=i;
}
void dfst(int i)
{
    int j;
    viz[i]=0;
    for(j=1;j<=at[i][0];j++)
        if(viz[at[i][j]])
            dfst(at[i][j]);

}
int main()
{
    citire();
    for(i=1;i<=n;i++)
        if(!viz[i])
                dfs(i);
    for(i=n;i>=1;i--)
        if(viz[post[i]])
    {
        nrc++;
        dfst(post[i]);
    }
    fout<<nrc<<'\n';
    fout.close();
    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 #1500 Nuclee

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1500 Nuclee 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 #1500 Nuclee