Codeforces #1475C Ball in Berland

문제

https://codeforces.com/problemset/problem/1475/C

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int a, b, k;
        cin >> a >> b >> k;
        vector<pair<int, int>> C(k);
        for(int i = 0; i < k; i++){
            cin >> C[i].first;
        }
        for(int i = 0; i < k; i++){
            cin >> C[i].second;
        }
        vector<int> A(a+1), B(b+1);
        for(int i = 0; i < k; i++){
            A[C[i].first]++;
            B[C[i].second]++;
        }
        ll ans = 0;
        for(int i = 0; i < k; i++){
            ans += k - A[C[i].first] - B[C[i].second] + 1;
        }
        cout << ans/2 << "\n";
    }
    return 0;
}

그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 서로 연결된 그래프 형태를 이분 그래프라고 한다.

무도회에 참여할 준비가 된 남녀 쌍의 정보를 이분 그래프에 나타내었을 때, 가능한 서로 다른 두 쌍의 개수를 구하는 문제이다.

선택한 쌍을 제외한 다른 쌍을 찾으려면 연결정보를 모두 확인해야하는 방법밖에 없는 줄 알았지만, 모든 간선의 개수는 k 개 임을 이용하여 시간안에 해결이 가능했다.

선택한 쌍이 (a, b) 라면 a, b 와 연결된 모든 간선의 개수를 k 에서 뺀 후 a, b 사이의 간선의 개수를 하나 더해주면, 선택한 (a, b) 와 같이 출전 가능한 쌍의 개수를 찾을 수 있다.

모든 간선에 대하여 똑같은 작업을 반복, 누적하면 가능한 경우의 수가 두번씩 중복된 값을 가진다. 2로 나누어 출력하면 정답이다.