특정 조건으로 그래프를 구성하는 C++ 프로그램

<시간/>

두 개의 숫자 N과 K가 있다고 가정합니다. N개의 요소가 있는 무방향 그래프가 있다고 가정합니다. N 정점은 다음 조건을 충족합니다 -

그래프는 단순하고 연결되어 있습니다.
정점은 1에서 N까지 번호가 매겨집니다.
M을 그래프의 간선 수라고 합시다. 모서리는 1에서 M까지 번호가 지정됩니다. 모서리의 길이는 1입니다. 모서리 i는 꼭지점 U[i]를 꼭지점 V[i]에 연결합니다.
i

그러한 그래프가 존재한다면 우리는 그 그래프를 구성해야 합니다. 그렇지 않으면 -1을 반환합니다.

따라서 입력이 N =5와 같으면; K =3이면 출력은

특정 조건으로 그래프를 구성하는 C++ 프로그램

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

출력