내용

글번호 803
작성자 heojk
작성일 2018-01-19 16:17:58
제목 코딩 테스트 1-2
내용 그래프 나누기 입력으로 그래프를 받아서 노드를 두 집합으로 분할하라. 단, 그래프의 전체 에지들 중 절반이상은 분할된 두 집합에 속하는 노드들을 잇는 것이어야 한다. [입력] 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 C가 주어지고, 이후 차례로 C개 테스트 케이스가 주어진다 (1≤C≤20). 각 케이스의 첫째 줄에 노드의 수 N(100,000이하)과 에지의 수를 나타내는 자연수 M(300,000이하)이 주어진다. 노드는 1부터 N까지 번호가 붙어 있다. 다음 M개의 줄에는 에지들이 하나씩 주어진다. 에지는 두 노드 번호의 (순서 없는) 쌍으로 주어진다. 같은 번호의 쌍이 두번 이상 주어지는 경우는 없다. [출력] 각 테스트 케이스에 대해서 출력은 3 줄로 구성된다. 첫 줄에는 두 자연수 N1과 N2가 주어진다. 다음 줄에는 N1개의 자연수가 있어야 하는데, 분할 중 첫번째 집합의 노드들이다. 마찬가지로 그 다음 줄에는 N2개의 자연수가 있어서 분할 중 두번째 집합의 노드들이다. [입출력 예] 입력 2 ← 총 2개의 테스트 케이스가 있다는 뜻 3 0 ← 1번 케이스의 시작줄 3 2 ← 2번 케이스의 시작줄 1 2 3 1 출력 1 2 ← 아무렇게나 나누어도 된다 1 2 3 1 2 1 2 3