Informatika gyűjtemény

Egy szinttel feljebb Fák izomorfiája

2004050607080910

NézetNyomtat

Fák izomorfiája

A 24 órás programozói verseny selejtezőjének 2. feladata, lecsupaszított változatban.

Feladat

Adott N fagráf, mindegyikük M csúcsú. Csoportosítsuk őket aszerint, hogy melyek izomorfak. Két gráf izomorf, ha csúcsaik között létezik kölcsönösen egyértelmű és él-tartó megfeleltetés. (Vagyis ha két csúcs össze van kötve az egyik gráfban, akkor a másikban is össze vannak kötve a megfelelőik.)

Bemenet

Az első sor a fák N, majd a csúcsok M számát adja meg. Ezután N sorban a fák leírása következik: minden fát M-1 számpár ad meg, az élek végpontjainak sorszáma. A számozás 0-tól kezdődik.

Kimenet

A kimenetben a fák sorszámait kell csoportosítani, egy sorba az izomorf fák azonosítói kerülnek. A sorrend tetszőleges.

Példa

Bemenet

3 5
0 1 1 2 1 3 3 4
3 4 1 3 0 3 3 2
4 0 2 0 3 4 1 4

Kimenet

0 2
1

Tesztadatok