10891번: Cactus? Not cactus?

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

참고로 본래 선인장 그래프의 정의는 '그래프에 속해 있는 모든 간선에 대해 최대 1개의 사이클에 포함된 것'이다.
문제에 제시된 정의는 살짝 다르므로 유의하자.


$O(n+m)$

dfs 탐색을 하다가 이미 방문했던 노드를 탐색하게 된다면 사이클을 이루는 것이다.
이 사이클을 이루는 노드들을 모두 체크해놓자.
이후에 체크된 노드를 다시 탐색하게 된다면 그 노드는 적어도 2개 이상의 사이클에 포함되어 있으므로 선인장 그래프가 아니다.
이러한 노드가 없다면 선인장 그래프이다.

#include<cstdio>
#include<stdlib.h>
#include<vector>
using namespace std;
const int MXN = 1e5;
int n, m, par[MXN + 1], ck[MXN + 1];
vector<int> adj[MXN + 1];
void f(int h) {
    ck[h]++;
    for (auto it : adj[h]) {
        if (it == par[h] || ck[it] == 2) continue;
        if (ck[it]) {
            for (int i = h; i^par[it]; i = par[i])
                if (ck[i]++ == 2) puts("Not cactus"), exit(0);
        }
        else par[it] = h, f(it);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    puts("Cactus");
    return 0;
}