Հարևանության ցուցակ – գրաֆի ներկայացում
Գրաֆերի ներկայացման ամենատարածված միջոցներից մեկը հարևանության ցուցակների կիրառումն է: Հարևանության ցուցակը գրաֆը ցուցակների զանգվածով ներկայացնելու եղանակ է. զանգվածի յուրաքանչյուր տարրը խորհրդանշում է գրաֆի որևէ գագաթ, իսկ 해당 գագաթին առնչվող ցուցակում նշել են բոլոր այն գագաթները, որոնք հարևան են նրան:
Տրված նկարում պատկերված ուղղորդված գրաֆի համար կարող ենք ստանալ նրա հարևանության ցուցակը.
g = [
[], # Անտեսում ենք գագաթ 0-ը
[2, 4], # Գագաթ 1
[5], # Գագաթ 2
[2], # Գագաթ 3
[], # Գագաթ 4
[6, 8], # Գագաթ 5
[4, 7], # Գագաթ 6
[8], # Գագաթ 7
[5], # Գագաթ 8
]
Ինչպես նկատում եք, այս գրաֆը հարևանության ցուցակով ներկայացնելը զգալիորեն ավելի կոմպակտ է, քան հարևանության մատրիցով տարբերակը, քանի որ մեր օրինակում կողերը քիչ են: Այնուամենայնիվ, որոշ դեպքերում, երբ կողերի քանակը բավականին մեծ է, գրաֆը հարևանության մատրիցով պահելը կարող է լինել ավելի արդյունավետ տարբերակ:
Առաջադրանք: Կողմերը դեպի Հարևանության ցուցակ
Տրված է չուղղորդված գրաֆ
v գագաթներով և e կողմերով։ Ձեզ խնդրում են գրել ծրագիր, որը ստանալով այդ գրաֆը, պետք է ստանա նրա հարևանության ցուցակը:Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
v (1 ≤ v ≤ 100 000) և e (1 ≤ e ≤ 100 000):Հաջորդ
e տողերում նշված են երկու ամբողջ թվեր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք ցույց են տալիս, որ գագաթ v1-ը կապված է գագաթ v2-ի հետ և հակառակը:Ելք
Ծրագիրը պետք է տպի տրված գրաֆի հարևանության ցուցակը։ Յուրաքանչյուր տող باید սկսվի գագաթի համարով, შემდეგ գրված լինի բութ-նկետ (:), ապա գագաթի բոլոր կապերը, որոնք պետք է տարանջատվեն բացատներով։ Գագաթների և կապերի հերթականությունը կամայական է:
Օրինակներ
Մուտք | Ելք |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 1: 2 4
2: 1 3 5
3: 2
4: 1 6
5: 2 6 8
6: 4 7 5
7: 8 6
8: 5 7 |
Բացատրություն
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB