एडजेसंसी मैट्रिक्स – ग्राफ़ का प्रतिनिधित्व
ग्राफ़ एक संरचना है, जो वर्टेक्स (नोड्स) और इन वर्टेक्स को जोड़ने वाली एज से मिलकर बनता है। ग्राफ़ का उपयोग वस्तुओं के बीच संबंधों या किसी नेटवर्क का मॉडल तैयार करने के लिए किया जा सकता है। अक्सर इन्हें शहरों, लोगों या अमूर्त संस्थाओं के बीच रिश्तों को दर्शाने के लिए भी इस्तेमाल किया जाता है।
ग्राफ़ या तो निर्देशित (Directed) हो सकता है या अनिर्देशित (Undirected)।
- निर्देशित ग्राफ़: इसमें सभी एज एक निश्चित दिशा रखती हैं—यानि एक वर्टेक्स से दूसरे वर्टेक्स तक “सड़क” होती है, लेकिन ज़रूरी नहीं कि वापस आने का रास्ता भी हो। यह एक-तरफ़ा सड़क की तरह है। फिर भी, निर्देशित ग्राफ़ में दोनों दिशाएँ हो सकती हैं, बस उन्हें स्पष्ट रूप से चिह्नित किया जाता है (जैसे ग्राफ़ में वर्टेक्स 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).
- अनिर्देशित ग्राफ़: इसकी एज पर कोई दिशा नहीं होती, जिसका अर्थ है कि यदि दो वर्टेक्स के बीच एक एज है, तो वे दोनों तरफ़ से आपस में जुड़े हुए हैं।
ग्राफ़ को दर्शाने के अनेक तरीक़ों में से एक है एडजेसंसी मैट्रिक्स (Adjacency Matrix)। यह एक चौकोर मैट्रिक्स होता है, जो पूरे ग्राफ़ का प्रतिनिधित्व करता है। इस मैट्रिक्स में प्रत्येक पंक्ति (row) और स्तंभ (column) ग्राफ़ के एक वर्टेक्स से संबंधित होते हैं। यदि दो वर्टेक्स के बीच एक एज मौजूद है, तो उस पंक्ति और स्तंभ का मान 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 से जाने वाले कनेक्शन
]ध्यान दें कि यदि कोई एज द्वि-दिशात्मक (bidirectional) है, तो दोनों संबंधित वर्टेक्स के लिए 1 अंकित होगा।
साथ ही यह भी ध्यान दें कि यहां हमने वर्टेक्स को मैट्रिक्स में इंडेक्सिंग के हिसाब से थोड़ा अलग बनाया है। उदाहरण के लिए, यदि आप
g[0] ऐक्सेस करते हैं तो यह वास्तविक में “1” इंडेक्स वाले वर्टेक्स के सभी कनेक्शन लौटाएगा। आप चाहें तो 9 पंक्तियाँ और 9 स्तंभ बनाकर मैट्रिक्स को पूरी तरह तस्वीर में दिख रहे नंबरों से मिलान करा सकते हैं, लेकिन यह पूरी तरह आप पर निर्भर है 😎।चुनौती: Edges से Adjacency Matrix
आपको एक ऐसे ग्राफ़ की एडजेसंसी मैट्रिक्स प्राप्त करनी है, जिसमें
v वर्टेक्स और e एज हों।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
v (1 ≤ v ≤ 1000) और e (1 ≤ e ≤ 100 000) दिए जाते हैं।अगली
e पंक्तियों में प्रत्येक में दो पूर्णांक v1, v2 (1 ≤ v1, v2 ≤ v) दिए होते हैं, जिनका अर्थ है कि वर्टेक्स v1 वर्टेक्स v2 से जुड़ा हुआ है और इसका उल्टा भी सही है।आउटपुट
कार्यक्रम को दिए गए ग्राफ़ की एडजेसंसी मैट्रिक्स को प्रिंट करना चाहिए। प्रत्येक पंक्ति में मूल्यों को स्पेस से अलग किया जाना चाहिए।
उदाहरण
Input | Output |
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