루미 알고리즘

#1331플래티넘Wikipediaspråk

PO 2013 온라인 예선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Om jag säger “Sortera orden [zebra, anka, duva]!” så svarar du snabbt [anka, duva, zebra]. Lätt, va? Det gäller även om du inte känner igen ordens innebörd eller alla tecken i språket, typ [fünf, como estás, désolé]. Vi kan ju svenska och engelska och vet att troligen är svaret [como estás, désolé, fünf]. Ännu inte så svårt. Men troligen finns det få programmeringsolympiaddeltagare som kan sortera sådana ordlistor så fort kinesiska, persiska och andra icke-latinska tecken är inblandade i ordlistorna. Hur skulle du jämföra ett engelskt ord med ett persiskt ord? En av problemförfattarna vet visserligen hur persiska ord ska uttalas, men utan den kunskapen blir det svårt.

Antag nu att vi vill sammanställa en sorterad lista av ord. Till vår hjälp har vi ett antal personer som vardera känner igen ett antal ord och vet deras inbördes ordning. Vi behöver inte ta med alla ord i vår ordlista, men vi vill vara helt säkra på att de ord vi tar med är rätt sorterade. Skriv ett program som beräknar det maximala antalet ord vi kan ha med i ordlistan, och skriver ut en giltig ordlista med detta antal ord.

Indata

För enkelhets skull behöver du inte läsa in själva orden, utan varje ord representeras istället av ett index mellan 0 och N-1. På första raden av indatan står två heltal N (1 ≤ N ≤ 130000) och P (1 ≤ P ≤ 10^5), där N är antalet ord och P är antalet personer. Därefter följer P rader som vardera anger ordningen på de ord som en viss person känner till. Varje sådan rad börjar med ett heltal 2 ≤ p_i ≤ 25 som beskriver hur många ord personen i fråga känner till den inbördes sorteringen för. Sedan följer p_i heltal i intervallet 0 till N-1, indexen för de ord personen känner till i den ordning de ska sorteras. Det är inte säkert att alla de N orden finns med på någon lista, och ett ord kan givetvis förekomma på flera listor. Det kommer inte att finnas motsägelser i indatan.

Utdata

Skriv först ut ett heltal: det maximala antalet ord M i en garanterat korrekt sorterad ordlista. Skriv därefter ut en rad med en sådan sorterad ordlista innehållandes de M ordindexen. Om det finns flera tänkbara sådana ordlistor kan programmet skriva vilken som helst av dem.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängGränser
130N ≤ 30
270Inga ytterligare begränsningar.

예제

예제 1

입력
4 5
2 0 1
2 2 3
2 2 1
2 1 3
2 0 2
출력
4
0 2 1 3 

예제 2

입력
10 6
2 5 7
3 4 2 0
4 4 8 1 0
3 8 2 5
2 0 6
3 4 7 9
출력
6
4 8 2 5 7 9 

출처 표기

출처: Programmeringsolympiaden 2013년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.