[BOJ 1762] 평면그래프와 삼각형

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

1762번: 평면그래프와 삼각형

Tag : sqrt?

 

문제요약

평면그래프 G(v, e)가 주어질 때 크기가 3인 사이클의 개수를 구하라. 

 

풀이

 

sol 1)

평면그래프는 \( |E| \leq 3|V| - 6 \)을 만족하기 때문에 m은 최대 \(300000 - 6\)입니다. 

가장 직관적인 풀이를 생각해보겠습니다. 

 

모든 간선 (i ->  j)를 순회하며 (i -> k), (j -> k) 가 모두 존재하는 k의 개수를 세어주고 중복을 제거해주면 될 듯합니다. 

v를 G의 인접리스트로 정의하면 간단히 구할 수 있습니다.

 

for(auto &[i, j] : edge) {
	for(auto &k : v[j]) ans += mp[i][k];
}
cout << ans / 3 << endl;

+ 이 나이브가 통과해서 데추주 넣었습니다 

 

이 때 두가지 경우를 생각해볼 수 있습니다. 

1. \(sz(v[i]) \leq N^{\frac{1}{2}}\) or \(sz(v[j]) \leq N^{\frac{1}{2}}\)

2. \(sz(v[i]) > N^{\frac{1}{2}}\) and \(sz(v[j]) > N^{\frac{1}{2}} \)

[1]의 경우에는 \(O(N^{\frac{1}{2}})\)에 해결 가능합니다. 

[2]는 최대 \(O(N)\)이 걸리지만 이에 해당되는 간선은 최대 \(O(N^{\frac{1}{2}})\)뿐입니다.

Degree가 \(N^{1/2}\)초과인 정점의 개수는 \(O(N^{1/2})\)개이고 이 정점들만을 포함하는 부분 그래프 또한 평면그래프입니다.

그래서 해당하는 간선은 최대 \( O(N^{ \frac{1}{2} }) \)개입니다.

 

시간복잡도 :  \(O(N ^ {\frac{3}{2}} log{N}) \)

 

+ \(O(N^{\frac{3}{2}}log{N})\)이 꽤 넉넉하게 도는걸 보면 실제 시간복잡도는 더 타이트한 듯 합니다.

+ \( O(\binom{5}{2} N log N ) \)풀이를 찾았습니다.

 

전체코드

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

int n, m, ans = 0;
vector<int> v[101010];
vector<pair<int, int>> edge;

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[2000000],*d;
    void set() {
        struct stat st;fstat(0,&st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    }
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(T x) {
        if(x<0) *d++='-', x=-x;
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=10;
    }
};

FASTIO<int> IO;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
    
    IO.set();
    n = IO.get(); m = IO.get(); assert(m <= 3 * n - 6);
    edge.resize(m);
    for(int i=1; i<=m; i++) {
        int p = IO.get(), q = IO.get();
        v[p].push_back(q); v[q].push_back(p);
        edge.push_back({p, q});
    }
    for(int i=1; i<=n; i++) sort(v[i].begin(), v[i].end());
    for(auto &[i, j] : edge) {
        if(v[i].size() < v[j].size()) swap(i, j);
        for(auto &k : v[j]) ans += binary_search(v[i].begin(), v[i].end(), k);
    }
    cout << ans / 3 << endl;
}

---

sol 2)

 

그때그때 가장 작은 Degree를 가진 정점을 고릅니다. 평면그래프는 \(|E| \leq 3|V| - 6\)을 만족하기 때문에

고른 정점의 Degree는 항상 5 이하입니다. \( \frac{6|V| - 12}{ |V| } < 6\) 

평면그래프에서 정점 한개 삭제해도 평면그래프이니 Degree는 계속 5 이하로 유지됩니다.

이제 고른 정점에서 모든 두 정점 조합을 살펴보면 됩니다. 

현재 정점을 기준으로 탐색을 모두 마친 후에는 그래프에서 현재 정점을 삭제합니다.

이웃한 정점들의 차수도 갱신해야겠죠. 

 

시간복잡도 : \(O(\binom{5}{2} N log N) \)

 

전체코드

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

int n, m, ans = 0;
set<pair<int, int>> st;
set<int> v[101010];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
    
    cin >> n >> m; assert(m <= 3 * n - 6);
    for(int i=0; i<m; i++) {
        int p, q; cin >> p >> q;
        v[p].insert(q);
        v[q].insert(p);
    }
    for(int i=1; i<=n; i++) st.insert({v[i].size(), i});
    while(st.size()) {
        auto [sz, x] = *st.begin(); st.erase(st.begin());
        for(auto &i : v[x]) for(auto &j : v[x])
            ans += i != j and v[i].find(j) != v[i].end();
        for(auto &i : v[x]) {
            st.erase({v[i].size(), i});
            v[i].erase(x);
            st.insert({v[i].size(), i});
        }
    }
    cout << ans / 2 << endl;
}