資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究用特定的條件構建圖的 C++ 程式
假設我們有兩個數字 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，則輸出將是
步驟
為了解決這個問題，我們將按照以下步驟進行 −
if k > (n - 1) * (n - 2) / 2, then: print -1 print ((n - 1) * (n - 2) / 2 - k + n - 1) for initialize i := 1, when i < n, update (increase i by 1), do: print pair (1, i + 1) count := (n - 1) * (n - 2) / 2 - k for initialize i := 2, when i <= n, update (increase i by 1), do: for initialize j := i + 1, when j <= n, update (increase j by 1), do: if count <= 0, then: return print pair (i, j) (decrease count by 1)
示例
讓我們看看以下實現來獲得更好的理解 −
#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
更新於： 2022-03-03
482 次瀏覽
廣告