[BOJ 10891] Cactus? Not cactus?

문제

---

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

풀이

---

선인장이란 양방향 그래프의 일종인데, 각 정점에 대해 자기 자신으로 돌아오는 경로(단순 사이클)가 하나 이하인 그래프이다.

캠프 강의에선 BCC로 묶은 후 크기가 3 이상인 BCC에 대해 속한 엣지의 수와 노드의 수가 같은지, 또 각 노드 별로 속한 크기 3 이상의 BCC가 최대 1개인지 확인함으로써 그래프가 선인장인지 아닌지 판별했다.

하지만 dfs tree만 생각해 봐도 문제를 풀 수 있다.

visit이란 배열에 dfs 과정에서 각 노드를 몇 번이나 방문했는지를 기록하고, parent란 배열에 부모 노드를 기록한다.

어떤 노드에서 back edge가 존재하면 사이클을 이루는 것이므로 사이클에 포함된 노드들의 visit 값을 하나씩 늘려준다.

이 과정에서 visit 값이 2가 되는 노드가 존재하면 선인장이 아니게 되는 것이다.

코드

---

#include <iostream>
#include <vector>

using namespace std;

int n, m, a, b, i, idx = 1;
vector<vector<int>> graph;
int dfsn[100001], parent[100001], visit[100001];

void dfs(int cur, int par) {
    dfsn[cur] = idx++;
    visit[cur] += 1;
    parent[cur] = par;

    for (int nxt : graph[cur]) {
        if (nxt == par || dfsn[nxt] >= dfsn[cur]) continue;

        if (visit[nxt]) {
            int temp = cur;
            while (temp != parent[nxt]) {
                if (visit[temp] == 2) {
                    cout << "Not cactus";
                    exit(0);
                }
                visit[temp] += 1;
                temp = parent[temp];
            }
        }
        else dfs(nxt, cur);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    graph = vector<vector<int>>(n + 1);

    for (i = 0; i < m; i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, -1);
    cout << "Cactus";

    return 0;
}

32MB라는 극악의 메모리 제한으로 파이썬, pypy 모두 정답자가 없었다.

그래서 나도 꾸역꾸역 C++로 코드를 짰다.

사실 이전에 여러 방법을 시도했었는데, 그 과정에서 반례가 있음에도 AC를 받는 코드들이 존재해서 데이터 추가를 요청했다.

Input
4 5
1 2
2 3
3 4
4 5
2 4

Output
Not cactus