백준 15339번 Counting Cycles

문제 요약

정점이 $N$개 있고 간선이 $M$개인 연결그래프가 주어진다. 이 때, 단순 사이클의 갯수를 구해야 한다.

$ 3 \le N \le 100000$, $ N-1 \le M \le N+15$

풀이

제한이 10만이었구나 왜 20만으로 착각했을까

일단 간선의 제한이 매우 수상하다. $N+15$라는 저 어정쩡한 제한을 보라.

일단 간선이 $N-1$일 때는 트리다. 사이클이 존재하지 않는 그래프고, $N$개일 때는 당연히 사이클은 하나다.

트리에서 간선이 하나 추가될 때 마다 사이클이 생겨난다. 즉, 이렇게 해서 생길 수 있는 사이클은 최대 16개다.

여기서 중요한 사실이 있는데 생길 수 있는 사이클은 사이클끼리 겹치게 해서 홀수번만 겹쳐진 간선들을 사용하는 사이클 외에는 존재 할 수 없다. 는 강한 추측을 갖고 문제를 풀면 된다.

이와 관련해서는 Cyle basis라는 것으로 어떻게 잘 정의되어 있나보다. 물론 그런 걸 나는 모르고 Xortest Path라는 문제를 풀다가 얻은 지식이다.

좀 더 잘 정리해보면 단순 사이클이 될 수 있는 것은 back edge로 생겨난 단순 사이클의 조합들 중에서 밖에 존재하지 않는 다는 것이다. 사실 그림을 그려서 생각해보면 굉장히 그럴 거 같이 생겨먹었다.

그리고 back edge로 생겨나는 사이클은 최대 16개이다. 이 갯수를 $k$라고 부르겠다.

그러면 우리가 시도해볼 조합은 $2^k$만큼 있는 것인데 한 조합당 판별에 걸리는 시간복잡도가 $O(N+M)$으로 간단히 터진다.

그런데 정말 모든 그래프가 필요할까? 대부분의 정점은 차수가 1이거나 2일것이다. 그리고 이런 정점들은 사이클을 결정짓지 않고 어떤 사이클에 속하거나 사이클에 속하지 않을 것이다.

당연히 차수가 1인 정점은 사이클에 속하지 못하니까 전부 지워준다. 차수가 2인 정점들도 전부 지워줘도 문제 없다. 이 때 주의할 것이 지워주면서 자신이 연결 되어 있는 다른 두 정점을 서로 연결해줘야 하며, 자신으로 인해서 사이클이 생겨나는 정점이라면 이는 지우면 안된다.

어떤 말이냐면 1 - 2, 2 - 4, 4 - 3, 1 - 3 의 간선들로 정점 1, 2, 3, 4이 연결되어 있다고 하자. 그리고 정점 2의 차수가 2니까 지워주고 1과 4를 이어 준다.

그 다음에 4를 지우려고 보니까 내가 지워 지면 1과 3 사이에 간선이 두 개 생기면서 사이클이 지워지는 효과가 생긴다. 물론 이런 중복 간선을 잘 처리할 자신이 있으면 깡으로 해도 된다. 난 자신이 넘친다. 처리 못할 자신이 넘쳐난다. 그래서 그런 짓은 안한다.

이렇게 그래프를 압축하면 정점의 수가 $O(k)$정도인 그래프로 압축을 할 수 있다.

사이클의 갯수와는 상관이 없는 정점만 지웠으므로 사이클의 갯수는 아무 상관이 없다.

이제 한 조합당 판별에 걸리는 시간복잡도가 $O(k)$로 줄었다. 따라서, 총 시간복잡도는 $O(N+M+k2^k)$정도가 될 것이다.

조합당 판별하는 방법은 사용할 사이클을 고른 다음에 그 사이클의 간선을 전부 체크한다. 그 다음 모든 간선을 보면서 체크된 횟수가 홀수인 간선을 사용해서 정점들을 합쳐주고 컴포넌트가 하나인지, 모든 정점의 차수가 2인지 판별하면 된다.

구현량이 많다.

#include<bits/stdc++.h>
using namespace std;
vector<set<int>> G(200005);
int N, M;
int depth[50], parent[50], parent_edge[50];
vector<vector<int>> cycles;
set<int> cycle_edges;
int parents[50];
int Find(int a) {
    if(parents[a] < 0) return a;
    return parents[a] = Find(parents[a]);
}

bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if(u == v) return false;
    parents[v] = u;
    return true;
}

void dfs(const vector<vector<pair<int,int>>> &G, int cur, int par, int d) {
    depth[cur] = d;
    for(pair<int,int> p : G[cur]) {
        int nxt = p.first;
        if(nxt == par) {
            parent_edge[cur] = p.second;
            continue;
        }
        if(depth[nxt] == -1) {
            parent[nxt] = cur;
            dfs(G, nxt, cur, d+1);
        }
        else cycle_edges.insert(p.second);
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0;i<M;++i) {
        int u, v; cin >> u >> v;
        G[u].insert(v);
        G[v].insert(u);
    }
    if(M == N-1) {
        cout << 0 << '\n';
        return 0;
    }
    if(M == N) {
        cout << 1 << '\n';
        return 0;
    }
    // remove vertex with degree one
    queue<int> q;
    for(int i=1;i<=N;++i) if(G[i].size() == 1) q.push(i);
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int nxt : G[cur]) {
            G[nxt].erase(cur);
            if(G[nxt].size() == 1) q.push(nxt);
        }
        G[cur].clear();
    }
    // compress segment with degree two
    for(int i=1;i<=N;++i) if(G[i].size() == 2) {
        q.push(i);
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            if(G[cur].size() == 2) {
                auto it = G[cur].begin();
                int s = *it++, e = *it;
                if(G[s].count(e)) continue;
                G[cur].erase(s);
                G[cur].erase(e);
                G[s].insert(e);
                G[e].insert(s);
                G[s].erase(cur);
                G[e].erase(cur);
                if(G[s].size() == 2) q.push(s);
                if(G[e].size() == 2) q.push(e);
            }
        }
    }
    set<int> vertex;
    vector<int> v, rev(200005);
    vector<pair<int,int>> edges;
    for(int i=1;i<=N;++i) if(G[i].size()) {
        if(vertex.find(i) == vertex.end()) {
            rev[i] = v.size();
            v.push_back(i);
        }
    }
    set<pair<int,int>> edge;
    vector<vector<pair<int,int>>> comp_G(v.size());
    for(int cur : v) {
        for(int nxt : G[cur]) {
            int u = min(rev[cur], rev[nxt]);
            int v = max(rev[cur], rev[nxt]);
            if(edge.find({u, v}) != edge.end()) continue;
            edge.insert({u, v});
            comp_G[u].emplace_back(v, edges.size());
            comp_G[v].emplace_back(u, edges.size());
            edges.emplace_back(u, v);
        }
    }
    memset(depth, -1, sizeof(depth));
    dfs(comp_G, 0, -1, 0);
    for(int x : cycle_edges) {
        vector<int> cycle;
        int back_edge = x;
        int u = edges[back_edge].first;
        int v = edges[back_edge].second;
        if(depth[u] > depth[v]) swap(u, v); // u < v
        cycle.push_back(x);
        while(depth[u] < depth[v]) {
            cycle.push_back(parent_edge[v]);
            v = parent[v];
        }
        while(u != v) {
            cycle.push_back(parent_edge[u]);
            cycle.push_back(parent_edge[v]);
            u = parent[u];
            v = parent[v];
        }
        cycles.push_back(cycle);
    }
    int n = cycles.size();
    int ans = 0;
    for(int i=1;i<(1<<n);++i) {
        vector<int> cnt(edges.size(), 0);
        for(int j=0;j<n;++j) if(i & (1<<j)) {
            for(int x : cycles[j]) cnt[x]++;
        }
        vector<int> degree(v.size(), 0);
        set<int> s;
        int comp_cnt = 0;
        memset(parents, -1, sizeof(parents));
        for(int i=0;i<edges.size();++i) if(cnt[i]%2) {
            int u = edges[i].first;
            int v = edges[i].second;
            if(!degree[u]) ++comp_cnt;
            if(!degree[v]) ++comp_cnt;
            degree[u]++;
            degree[v]++;
            s.insert(u);
            s.insert(v);
            if(Union(u, v)) --comp_cnt;
        }
        if(comp_cnt != 1) continue;
        bool flag = true;
        for(int x : s) flag &= degree[x] == 2;
        ans += flag;
    }
    cout << ans << '\n';
    return 0;
}