मान लीजिए हमारे पास दो संख्याएं N और K हैं। N तत्वों वाला एक निदेशित ग्राफ पर विचार करें। N शीर्ष निम्नलिखित शर्तों को पूरा करते हैं:
- ग्राफ सरल और जुड़ा हुआ है
- शीर्ष 1 से N तक गिने जाते हैं
- मान लें M ग्राफ में किनारों की संख्या है। किनारों को 1 से M तक गिना जाता है। किनारे की लंबाई 1 है। और किनारा i शीर्ष U[i] को शीर्ष V[i] से जोड़ता है।
- ठीक K शीर्ष युग्म (i, j) हैं जहां i < j, जैसे कि उनके बीच की सबसे छोटी दूरी 2 है।
यदि ऐसा ग्राफ मौजूद है, तो हमें उस ग्राफ का निर्माण करना है। अन्यथा -1 वापस करें।
उदाहरण के लिए, यदि इनपुट N = 5; K = 3 है, तो आउटपुट होगा:
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
यदि k > (n - 1) * (n - 2) / 2, तो: -1 प्रिंट करें ((n - 1) * (n - 2) / 2 - k + n - 1) प्रिंट करें i := 1 से n-1 तक, करें: युग्म (1, i + 1) प्रिंट करें count := (n - 1) * (n - 2) / 2 - k i := 2 से n तक, करें: j := i + 1 से n तक, करें: यदि count <= 0, तो: वापस करें युग्म (i, j) प्रिंट करें count घटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void solve(int n, int k){ if (k > (n - 1) * (n - 2) / 2){ cout << -1 << endl; } cout << (n - 1) * (n - 2) / 2 - k + n - 1 << '\n'; for (int i = 1; i < n; i++){ cout << 1 << ", " << i + 1 << '\n'; } int count = (n - 1) * (n - 2) / 2 - k; for (int i = 2; i <= n; i++){ for (int j = i + 1; j <= n; j++){ if (count <= 0){ return; } cout << i << ", " << j << '\n'; count--; } } } int main(){ int N = 5; int K = 3; solve(N, K); } इनपुट
5, 3
आउटपुट
7 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5
