Říká se, že přátelé mých přátel jsou i mými přáteli. Mějme komunitu lidí, ve které každý může mít pár přátel, se kterými se zná přímo. Zároveň, podle známého rčení, pokud Adam je přítel Bena a Ben je přítel Cecílie, tak Adam je přítelem Cecílie. Aplikací tohoto pravidla se nám rozrůstá naše skupinka přátel. Naším úkolem bude najít největší skupinku na základě vstupních dat.
Napište program, který na základě vstupních dat:
population_size: celková velikost naší komunityfriendships: seznam přímých přátelství ve tvaru[(1,2),(2,3),(4,5),(4,6), (6,7), ...]
Identifikuje největší skupinku přátel a řekne nám, jak je velká.
Co se touto úlohou naučím a o čem si něco přečíst?
- Datová struktura Graf.
- Procházení grafu, podgraf, komponenta grafu.
Kde se s touhle úlohou typově setkám?
Tam, kde hrají roli uzly (entity) a spojení mezi nimi. Například v počítačových sítích mohou routery či počítače reprezentovat vrcholy. Můžeme si položit otázku: "vidí" se všechny počítače mezi sebou? Kolik existuje nezávislých podsítí?
Úroveň znalostí
Středně pokročilý