15. 차수열

차수열

백준 마라톤 문제들을 풀다가 차수열이라는 태그가 붙은 문제들이 몇개 나와서 공부를 해보았다.
처음보는 단어라서 뭔가 했는데 어떤 그래프의 모든 정점 차수를 모아 만들어서 차수열(degree sequence)이라고 한다.

재밌어 보여서 태그가 붙어있는 모든 문제를 풀어보았고, 여러 그래프나 트리에서의 성질을 공부할 수 있었다.
공부한 이론, 성질과 문제 풀이를 간단하게 적어보려고 한다.

차수열 관련 이론

---

문제

난이도 순으로

Y (S3, 31217)

그래프가 주어지고 그 중 4개의 정점을 선택했을 때 Y 형태로 정점 1개에 나머지 3개가 붙어있는 모양이
총 몇개인지 구하는 문제이다.

그래프의 모든 정점에 대해 차수를 구하고, 차수를 n이라 하면 n(n-1)(n-2)/6을 계산해 더하면 된다.

    for(int i=0;i<m;i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    ans=0;
    for(int i=1;i<=n;i++){
        int sz=v[i].size();
        if(sz>=3){
            ans+= sz*(sz-1)*(sz-2)/6;
        }
        ans%=mod;
    }
    cout << ans;

Парное пугание (G5, 28570)

n과 k가 주어지고 n명의 아이들은 각각 1번 또는 k번의 짝을 지어서 나가야 한다.
n명에 대해 있을 때 가능하다면 한번만 짝을 지어야하는 학생의 수를 출력하고 불가능하면 -1을 출력한다.

우선 가장 먼저 생각나는 것은 k+1개의 정점을 가진 star 형태의 그래프이다.
중심에 있는 아이는 k개의 짝을 지을 수 있고, 나머지 아이는 1번의 짝만 짓게 된다.

그렇게 확장을 시켜보면 가능한 그래프는 star에 star가 연결된 형태여야만 한다.

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long mod = 1'000'000'007;
    using P=pair<int,int>;

    long long a, b, c, d;
    long long ans = 0;

    cin >> n >> m;

    if(n==m+1){
        cout<<m;
        return 0;
    }
    n-=(m+1);

    if(n%(m-1)==0){
        cout << m+n/(m-1)*(m-2);
    }
    else cout<<-1;

    return 0;
}

Autobiography (G4, 31110)

각 테스트케이스에 대해 정점과 간선이 주어지고 무방향 그래프이다.
각 정점은 b또는 o의 알파벳을 가진다.
이 때 이어져있는 서로 다른 정점 4개를 골라 bobo를 만들 수 있는 경우의 수를 출력한다.