Ադյաչենթի մատրից (Adjacency Matrix) - Գրաֆի ներկայացում
Գրաֆը մի կառուցվածք է, որը կազմված է գագաթներից (nodes/vertices) և կողերից (edges), որոնք կապում են այդ գագաթները։ Գրաֆները կարող են կիրառվել տարբեր օբյեկտների կամ ցանցերի հարաբերությունները ներկայացնելու համար։ Դրանք հաճախ օգտագործվում են քաղաքների, մարդկանց կամ նույնիսկ ինչ-որ 추աբ Եր:
Գրաֆները կարող են լինել ուղղորդված և անուղղորդ.
- Ուղղորդված գրաֆեր: Բոլոր կողերը ունեն ուղղություն, այսինքն՝ կարող է լինել «ճանապարհ» մեկ գագաթից դեպի մյուսը, սակայն հակառակ ուղղությունը պարտադիր չէ, որ լինի։ Դա կարելի է նմանացնել միակողմանի ճանապարհի։ Այնուամենայնիվ, նույն գրաֆում հնարավոր է ունենալ երկու ուղղություններով կապեր (օրինակ, գագաթներ 5 և 8–ի միջև գրված նկարում):
Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
- Անուղղորդ գրաֆեր: Կողերն ուղղություն չունեն, অর্থাৎ եթե կա կող երկու գագաթների միջև, ապա այդ գագաթները կապվում են միմյանց հետ երկու ուղղություններով էլ:
Գրաֆի ներկայացմանหนึ่งandomԳրամчиси fromգත of պատրաստ մի ձևերից մեկն Ադյաչենթի մատրից (Adjacency Matrix) օգտագործելն է։ Այն քառակուսի մատրից է, որն ամբողջությամբ ներկայացնում է գրաֆը։ Մատրիցի յուրաքանչյուր տող և սյուն համապատասխանում են գրաֆի մի գագաթի։ Եթե երկու գագաթների միջև կա կող, ապա մատրիցի համապատասխան դաշտը նշանակվում է 1։ Հակառակ դեպքում այն 0 է։
Վերոնշյալ ուղղորդված գրաֆի համար, Ադյաչենթի մատրիցի օրինակը կարող է այսպիսին լինել.
g = [
# 1 2 3 4 5 6 7 8
[0, 1, 0, 1, 0, 0, 0, 0], # Գագաթ 1-ից դուրս եկող կապերը
[0, 0, 0, 0, 1, 0, 0, 0], # Գագաթ 2-ից դուրս եկող կապերը
[0, 1, 0, 0, 0, 0, 0, 0], # Գագաթ 3-ից դուրս եկող կապերը
[0, 0, 0, 0, 0, 0, 0, 0], # Գագաթ 4-ից դուրս եկող կապերը
[0, 0, 0, 0, 0, 1, 0, 1], # Գագաթ 5-ից դուրս եկող կապերը
[0, 0, 0, 1, 0, 0, 1, 0], # Գագաթ 6-ից դուրս եկող կապերը
[0, 0, 0, 0, 0, 0, 0, 1], # Գագաթ 7-ից դուրս եկող կապերը
[0, 0, 0, 0, 1, 0, 0, 0], # Գագաթ 8-ից դուրս եկող կապերը
]Ուշադրեք, որ եթե գագաթների միջև կա երկկողմանի կապ, ապա երկու դիրքերում էլ գրվում է 1:
Նկատեք նաև, որ մենք փոխել ենք կողերի ինդեքսավորումը։ Այսինքն, եթե մենք կանչենք
g[0], կստանանք այն կապերը, որոնք վերաբերում են թվով 1 (պատկերի մեջ) գագաթին։ Մենք կարող էինք օգտագործել 9 տող և 9 սյուն, որzać......Առաջադրանք: Edges to Adjacency Matrix
Տրված է գրաֆ, որը ունի
v գագաթ և e կող։ Պահանջվում է գտնել նրա adjacency matrix-ը։Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թիվ
v (1 ≤ v ≤ 1000) և e (1 ≤ e ≤ 100 000)։Հաջորդ
e տողերից յուրաքանչյուրում գրված են երկու ամբողջ թվեր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք նշանակում են, որ գագաթ v1-ը կապված է v2 գագաթին և հակառակը:Ելք
Ծրագիրը պետք է տպի տրված գրաֆի adjacency matrix-ը։ Յուրաքանչյուր տողի արժեքները պետք է բաժանված լինեն բացատանիշով։
Օրինակներ
Մուտք | Ելք |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB