레이팅 미적용*참고: 이 문제의 시간 제한은 3초로, 기본값보다 50% 크다. 메모리 제한은 기본값의 두 배이다.*
농부 존의 \(N\) (\(2\le N\le 2\cdot 10^5\))마리 소(\(1\dots N\)로 번호가 매겨져 있다) 사이에는 처음에 \(M\) (\(1\le M\le 2\cdot 10^5\))쌍의 친구 관계가 있다. 소들은 한 마리씩 휴가를 떠나 농장을 나간다. \(i\)일째에 \(i\)번째 소가 농장을 떠나고, 그 시점에 아직 농장에 남아 있는 \(i\)번째 소의 친구들끼리는 모두 서로 친구가 된다. 총 몇 개의 새로운 친구 관계가 만들어지는가?
Problem credits: Benjamin Qi
채점 방식
- 테스트 케이스 2-3은 \(N\le 500\)을 만족한다.
- 테스트 케이스 4-7은 \(N\le 10^4\)를 만족한다.
- 테스트 케이스 8-17은 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에는 소 \(u_i\)와 \(v_i\)가 친구임을 나타내는 두 정수 \(u_i\)와 \(v_i\)가 주어진다 (\(1\le u_i,v_i\le N\), \(u_i\neq v_i\)). 같은 소의 순서 없는 쌍은 두 번 이상 주어지지 않는다.
새로 만들어진 친구 관계의 총 개수를 한 줄에 출력한다. 처음부터 이미 친구였던 소의 쌍은 포함하지 않는다.
7 6
1 3
1 4
7 1
2 3
2 4
3 55On day \(1\), three new friendships are formed: \((3,4)\), \((3,7)\), and \((4,7)\).
On day \(3\), two new friendships are formed: \((4,5)\) and \((5,7)\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Platinum