Els amics dels meus amics són els meus amics P11754


Statement
 

pdf   zip

html

En una coneguda xarxa social, les persones estableixen relacions d’amistat simètriques. Donada una xarxa social, es vol saber quants amics tenen certes persones fent servir allò de "els amics dels meus amics són els meus amics".

Entrada

L’entrada consta de tres parts: La primera conté dos nombres naturals n i m que corres­ponen al nombre de persones a la xarxa i el nombre de relacions d’amistat directes entre elles. Els identificadors de les persones són de 0 a n−1. La segona part conté la descripció de les relacions d’amistat directes: Per a cadascuna de les m relacions hi ha un parell de naturals x i y que indiquen que x i y són amics directes a la xarxa. L’ordre de les relacions d’amistats i dels parells no està prescrit, però es té que 0≤ x,y<n i xy. Finalment, a la tercera part de l’entrada hi ha una seqüència d’identificadors de persones.

Sortida

Per a cada identificador de persona p a la tercera part de l’entrada, cal escriure el nombre total d’amics de p i d’amics d’amics de p (tret d’ell mateix i sense repetits).

Public test cases
  • Input

    6 7
        0 1 
        2 1
        0 2
        4 1
        3 2
        3 4
        5 4
    0
    4
    0
    5

    Output

    4
    5
    4
    3
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Other languages
    English
    Official solutions
    Python
    User solutions
    Python