IOI 2020 day1 - Connecting Supertrees

문제 링크 : www.acmicpc.net/problem/19934

문제 소개

인접행렬이 주어진다. 이때 모든 값은 3이하이다. 이때 주어진 인접행렬을 만족하는 트리가 있는지 판단하고, 있다면 그 트리를 보여라.

문제 풀이(+의식의 흐름)

part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리

경로의 가짓수로 가능한 것은 0,1,2,3 인데, 각각의 경우에 대해서 두 노드가 어떤 식으로 배치 되어 있을지에 대해서 생각을 해보았다.

0가지일때: 둘은 같은 컴포넌트에 존재하지 않는다. 또한 0 이 아닌 두 노드는 항상 같은 컴포넌트에 존재해야 한다. 따라서 우리는 경우의 수가 0이 아닌 모든 쌍에 대해서 union &find 를 이용하여 같은 컴포넌트로 묶을 수 있다. 
이때 같은 컴포넌트 내에 존재하는 두 노드의 경로 경우의 수가 0으로 표시되어 있다면 불가능하다고 판단하면 된다.
또한, 앞으로 모든 경우는 컴포넌트 별로 분리해서 각 컴포넌트에 대해서만 처리해주면 된다.

1가지일때 : 트리 느낌이다.
2가지일때 : 사이클 느낌이다.
3가지일때 : 정사각형에 대각선을 하나 그은 듯한 느낌이다.

그런데 여기서 조금 더 생각을 해보니 한 가지 사실을 관찰했다. a->b 경로가 3가지라고 해보자.
a->c->b, a->b, a->d->b와 같은 느낌으로 되어있다고 하면 c->d 의 경로가 4가지 이상이 나오게 된다.
c->a->d, c->a->b->d, c->b->a->d, c->b->d. 이런식으로 최소 4가지가 나오게 된다.
하지만, 4이상의 값은 존재하지 않기 때문에 결과적으로 3가지 경로가 된다는 것도 말이 안된다. 따라서 주어진 값에 3이 있다면 이는 불가능한 경우이다.

이 관찰을 하고 굉장히 빠르게 나름 의미 있는 관찰로 분리를 해낸 것 같아서 행복했지만, 아래를 내려 배점을 보니 3이 있는 경우에 4점이 배점되어 있었다...즉, 큰 의미가 없었다는 것... 조금은 슬펐지만, 오히려 진정되고 차분히 집중을 할 수 있었다.

part 2. 경로가 1가지인 경우에 대한 관찰.

위에서 관찰한 내용들을 처리해주면, 우리가 앞으로 할 것은 경로가 1가지인 경우와 경로가 2가지인 경우에 따라서 어떤식으로 처리를 할 지를 생각해야 한다.

a->b 의 경로가 1가지라는 것은 무엇을 의미할까? a-b는 일방통행이라는 것을 의미한다. 그러면 임의의 어떤 점은 a에 가깝거나 b에 가깝게 된다. b에 가까운 점 c가 있다고 하자. b에서 c로 가는 모든 경로에 대해서 a에서는 a->>b->>c로 똑같이 갈 수 있다. 즉, 경로의 경우의 수에 대해서 1대1 대응이 된다는 것이다. 
따라서 a->b의 경로가 1이면 a와 b를 묶어서 생각할 수 있다. union&find를 이용하여 그룹을 지으면 된다. 이때 같은 그룹내에 경로의 가짓수가 2인 쌍이 있으면 불가능한 경우이다.

part 3. 경로가 2가지인 경우에 대한 관찰

0,1,3 가지 일때에 대해서는 배제하고 묶어서 이제 남은 모든 노드는 경로가 서로 2가지인 노드들만 남았다. 한 컴퍼넌트에 노드가 1개이면 처리를 해줄필요가 없고, 3개 이상이면 원형(사이클)로 싹 다 이으면 되며, 2개일때는 불가능하다.

part 4. 정리

1. 경우의 수가 3이 있으면 fail
2. 연결 경우의 수가 0이 아닌 애들로 grouping, 같은 그룹에 0인 쌍이 있으면 fail.
3. 한 그룹 내에서 연결 경우의 수가 1인 애들로 추가로 grouping, 이후에 같은 그룹내에 경로의 경우의 수가 2인 쌍이 있으면 fail
4. 2번의 같은 그룹 내에서 3번 그룹의 각각 하나씩 뽑아내어 사이클 형성. 이때 뽑아낸 갯수가 2개면 fail

코드

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;

#define ff first
#define ss second
#define pb push_back

vector<pii> v[101];
ll par[1010101];
ll gch[1010101];
vector<ll> gp[1010101];
vector<pii> edg;

ll fi(ll x){
    if(x==par[x]) return x;
    return par[x]=fi(par[x]);
}

void uf(ll a,ll b){
    a=fi(a);
    b=fi(b);
    if(a==b) return;
    par[b]=a;
}

int construct(std::vector<std::vector<int>> p) {
    ll n = p.size();
    ll i,j,k,l,m;

    for(i=0;i<=n;i++)
        par[i]=i;

    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            v[p[i][j]].pb({i,j});

    if(v[3].size()) return 0;

    for(auto k:v[1]){
        uf(k.ff,k.ss);
    }
    for(auto k:v[2]){
        uf(k.ff,k.ss);
    }
    for(auto k:v[0]){
        if(fi(k.ff)==fi(k.ss)) return 0;
    }

    ll cnt=0;

    for(i=0;i<n;i++){
        if(gch[fi(i)]==0){
            cnt++;
            gch[fi(i)]=cnt;
            gp[cnt].pb(i);
        }
        else{
            gp[gch[fi(i)]].pb(i);
        }
    }

    for(ll x=1;x<=cnt;x++){
        ll sz=gp[x].size();
        for(auto k:gp[x]) par[k]=k;
        vector<ll> vv;

        for(i=0;i<sz;i++){
            ll k=gp[x][i];
            for(j=i+1;j<sz;j++){
                ll l=gp[x][j];
                if(p[k][l]==1){
                    if(fi(k)!=fi(l)) edg.pb({k,l});
                    uf(k,l);
                }
            }
        }

        for(i=0;i<sz;i++){
            ll k=gp[x][i];
            for(j=i+1;j<sz;j++){
                ll l=gp[x][j];
                if(p[k][l]==2&&fi(k)==fi(l)) return 0;
            }
        }
        for(auto k:gp[x]){
            //printf("%d %d %d\n",x,k,par[k]);
            if(par[k]==k) vv.pb(k);
        }

        ll ssz=vv.size();
        if(ssz==2) return 0;
        for(i=0;i<ssz;i++){
            edg.pb({vv[i],vv[(i+1)%ssz]});
        }
    }
    vector<vector<ll>> answer;
    for (int i = 0; i < n; i++) {
        vector<ll> row;
        row.resize(n);
        answer.push_back(row);
    }

    for(auto k:edg){
        if(k.ff!=k.ss){
            answer[k.ff][k.ss]=1;
            answer[k.ss][k.ff]=1;
       }
    }
    build(answer);
    return 1;
}