[백준] 19535

https://www.acmicpc.net/problem/19535

19535번: ㄷㄷㄷㅈ

그래프 중에서 특정 조건을 만족하는 부분 그래프를 찾는 문제였다.

ㄷ 그래프는 모든 점마다 연결된  모든 점을 골라서, 그 두 개의 점에서 (연결된 모든 점 - 1) 끼리 곱해서 개수를 구했다. 그렇게 하면 위의 그림 파란 점처럼 두 개를 고르게 되는데, 중복되는 부분은 점의 이름 크기를 비교해서 큰 쪽만 사용하는 방식으로 제거했다.(인접리스트를 사용했다)

ㅈ 그래프는 모든 점마다 연결된 모든 점의 개수를 nC3 해서 구했다. 

 

코드 

#include <vector>
#include <iostream>
using namespace std;

int N,D,G;
vector<vector<int> > v(300001);

int nc3(int n){
    if(n<3) return 0;
    return n * (n-1) * (n-2) / 6;
}
int getD(int v1, int v2){
    return (v[v1].size()-1) * (v[v2].size()-1);
}

int main(){
    cin >> N;
    
    int a,b;
    for(int i=0;i<N-1;i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    //G
    for(int i=1; i<=N; i++){
        G += nc3(v[i].size());
    }
    //D
    for(int i=1; i<=N; i++){
        for(auto j=v[i].begin(); j != v[i].end(); j++){
            if(i < *j)
                D += getD(i, *j);
        }
    }

    if(D > G*3)
        printf("D\n");
    else if(D < G*3)
        printf("G\n");
    else
        printf("DUDUDUNGA\n");
}