시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 30 16 15 65.217%

문제

정점 N개로 이루어진 그래프에 단 하나의 간선이 숨겨져 있다. 이 간선은 A번 정점과 B번 정점을 연결하는 양방향 간선이다.

숨겨진 간선이 연결하는 두 정점의 번호 A, B를 찾아내는 프로그램을 작성하시오.

함수 목록 및 정의

여러분의 프로그램은 제공되는 "findVertices.h" 파일을 include 해야 한다.

여러분의 프로그램은 한 번 실행될 때마다 T개의 테스트 케이스를 처리해야 한다. 프로그램의 실행 시간은 주어지는 모든 테스트 케이스를 처리하는 데 걸린 시간으로 측정한다.

여러분은 아래와 같은 함수를 구현해야 한다.

  • void find(int N)
    • N은 그래프의 정점의 개수를 의미한다.
    • 이 함수는 테스트 케이스마다 정확히 한 번 호출된다.

여러분은 아래와 같은 함수를 호출할 수 있다.

  • int query(vector <int> U, vector <int> V, int p, int q)
    • 두 배열 U, V에 대응되는 수열을 U, V라 하자.
    • 수열 U, V의 길이는 M으로 동일해야 하며, 0 ≤ M ≤ 5,000을 만족해야 한다.
    • 모든 0 ≤ i < M에 대해, 1 ≤ UiN, 1 ≤ ViNUiVi 을 만족해야 한다.
    • 1 ≤ p ≤ N, 1 ≤ q ≤ Np ≠ q을 만족해야 한다.
    • query 함수는 아래와 같이 동작한다.
      1. 모든 0 ≤ i < M에 대해, Ui번 정점과 Vi번 정점을 연결하는 양방향 간선을 그래프에 추가한다.
      2. p번 정점과 q번 정점이 연결되어 있는지 판별한다.
      3. 1.에서 추가한 간선을 모두 그래프에서 제거한다.
      4. 2.에서 두 정점 pq가 연결되어 있었다면 1, 아니면 0을 반환한다.
    • 여러분은 query 함수를 테스트 케이스마다 최대 13회 호출할 수 있다.

여러분은 아래와 같은 함수를 호출해야 한다.

  • void answer(int a, int b)
    • a, b의 쌍은 문제에 주어진 두 정수 A, B의 쌍과 같아야 한다. 순서는 중요하지 않다.
    • answer 함수는 테스크 케이스마다 정확히 한 번 호출되어야 한다.

제공되는 Sample Grader는 실제 채점에 활용되는 Grader와 다를 수 있음에 유의하라.

입력

Sample Grader는 다음과 같은 정보를 표준 입력을 통하여 읽어들인다. 여러분은 어떠한 입력도 받으면 안된다.

첫번째 줄에 테스트 케이스의 총 개수를 의미하는 자연수 T가 주어진다.

두번째 줄부터 T개의 줄에 걸쳐, T개의 테스트 케이스에 관한 정보가 주어진다. (i+1)번째 줄에는 세 개의 자연수 N, A, B가 사이에 공백을 두고 주어진다(1 ≤ iT).

출력

Sample Grader는 다음과 같은 정보를 표준 출력을 통하여 출력한다. 여러분은 어떠한 출력도 하면 안된다.

Sample Grader는 첫번째 줄부터 T개의 줄에 걸쳐, 각 줄마다 여러분이 찾은 A, B 값을 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 1 ≤ T ≤ 500
  • 2 ≤ N ≤ 100
  • 1 ≤ A ≤ N
  • 1 ≤ B ≤ N
  • A ≠ B

제공 파일

예제 입력 1

2
4 3 2
5 1 2

예제 출력 1

2 3
1 2

다음은 위의 입출력 예제에 대해서, Sample Grader와 Interaction하는 과정을 나타낸 것이다.

여러분이 작성한 코드 Grader 설명
  T = 2 Grader에서 T의 값을 읽어들인다.
  N = 4, A = 3, B = 2 첫번째 테스트 케이스의 정보를 읽어들인다.
  find(4) 호출 find 함수는 매 테스트 케이스마다 단 한 번씩 호출된다.
query({1, 2}, {3, 4}, 1, 3) 호출    
  return 1 1번 정점과 3번 정점은 연결되어 있다.
answer(2, 3) 호출   여러분은 A = 2, B = 3라고 예상하였고, 이는 실제와 순서만 다를 뿐 값은 일치한다.
find(N = 4) 종료    
  N = 5, A = 1, B = 2 두번째 테스트 케이스의 정보를 읽어들인다.
  find(5) 호출  
answer(1, 2) 호출   여러분은 A = 1, B = 2라고 예상하였고, 이는 실제와 정확히 일치한다.
find(N = 5) 종료    

위의 Interaction 과정은 실제 정해와 전혀 관련이 없으며, 단지 이해를 돕기 위해 만든 예시임에 유의하라.

출처

High School > 경기과학고등학교 > 나는코더다 2019 송년대회 K번

  • 데이터를 만든 사람: sebinkim
  • 문제를 만든 사람: yclock

제출할 수 있는 언어

C++14, C++17

채점

  • 예제는 채점하지 않는다.