18195번 - 정점 찾기 언어 제한함수 구현

정점 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 ≤ U_i ≤ N, 1 ≤ V_i ≤ N, U_i ≠ V_i 을 만족해야 한다.
  • 1 ≤ p ≤ N, 1 ≤ q ≤ N, p ≠ q을 만족해야 한다.
  • query 함수는 아래와 같이 동작한다.
    1. 모든 0 ≤ i < M에 대해, U_i번 정점과 V_i번 정점을 연결하는 양방향 간선을 그래프에 추가한다.
    2. p번 정점과 q번 정점이 연결되어 있는지 판별한다.
    3. 1.에서 추가한 간선을 모두 그래프에서 제거한다.
    4. 2.에서 두 정점 p와 q가 연결되어 있었다면 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 ≤ i ≤ T).

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

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

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

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

• Sample Grader: grader.cpp
• findVertices.h: findVertices.h
• findVertices.cpp: findVertices.cpp