17275번 - 부족 전쟁 서브태스크
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 25 | 12 | 7 | 100.000% |
문제
어느 행성에 N개의 작은 부족들이 살고 있다. 편의상 1부터 N까지 번호를 부여하자.
- 임의의 서로 다른 두 부족은 서로 동맹 관계이거나 서로 적대 관계이다. 이 관계는 대칭적이다. 즉, 부족 A는 부족 B를 동맹이라 생각하나 B는 A를 적이라 생각하는 경우는 없다.
- 부족 A와 부족 B가 동맹이고, 부족 B와 부족 C가 동맹이라도 부족 A와 부족 C가 적대 관계일 수 있다.
- 임의의 서로 다른 세 부족에 대하여, 세 부족이 서로 동맹 관계인 경우를 "삼자 동맹 관계"라 하고, 세 부족이 서로 적대 관계인 경우를 "삼자 적대 관계"라 하자.
이 때, N개의 부족 내의 서로 다른 "삼자 동맹 관계"와 "삼자 적대 관계"들을 전부 합한 개수를 구하라.
예를 들어 N = 5이고 부족1-부족2, 부족1-부족3, 부족4-부족5가 서로 동맹 관계, 나머지 부족 쌍은 모두 적대 관계라고 가정하자. 이 경우 (2, 3, 4)와 (2, 3, 5) 가 "삼자 적대 관계"를 만족하고, "삼자 동맹 관계"는 없기 때문에 답은 2가 된다.
다른 예로 N = 5이고 부족1-부족2, 부족2-부족3, 부족1-부족3이 동맹인 경우 (1, 2, 3)은 "삼자 동맹 관계"이고, (1, 4, 5), (2, 4, 5), (3, 4, 5)는 "삼자 적대 관계"이기 때문에 답은 4가 된다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스 첫 줄에 N, M이 공백으로 구분 되어 주어진다.
다음 M줄에 걸쳐서 한 줄에 두 개의 정수 x, y가 주어지는데 이는 x와 y가 동맹임을 나타낸다.
입력으로 주어지는 동맹 관계는 언제나 1 ≤ x < y ≤ N을 만족하고, 같은 부족 쌍이 여러 번 주어지는 경우는 없다.
입력으로 주어지지 않은 부족 쌍은 적대관계라고 가정한다.
출력
각 테스트 케이스에 대해 한 줄에 동맹-반동맹 계수를 출력한다.
서브태스크 1 (4점)
- 3 ≤ N ≤ 200
- 1 ≤ M ≤ min(1,000, N × (N-1)/2)
서브태스크 2 (13점)
- 3 ≤ N ≤ 5,000
- 1 ≤ M ≤ min(1,000,000, N × (N-1)/2)
예제 입력 1
3 3 1 1 2 5 3 1 2 2 3 1 3 5 3 1 2 1 3 4 5
예제 출력 1
0 4 2
채점
- 예제는 채점하지 않는다.
© 2020 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 5층 509호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
