Cactus? Not cactus?
선인장! 아! 얼마나 그리운 이름인가!
고등학교 시절 학교에서 Cactus 그래프를 너무 좋아하는 친구가 있어서 Cactus 그래프는 일종의 "밈"처럼 불렸다.
드디어 Cactus에 도달했다! Cactus 그래프가 뭔지부터 살펴보자.
-> 각 정점에서 자신으로 오는 단순 사이클의 개수가 1개 이하인 그래프.
단순하다! 이제 이렇게 단순 사이클의 개수를 어떻게 판단할지 알아보자. 사실, 이 판단에는 "단절선"만 있으면 된다.
모든 정점에 대해 검사해도, 2*M개의 정점만을 검사하므로, 시간복잡도 제한에 걸릴 리는 없다. 이제 제일 중요한 "사이클 검사법"을 알아보자.
-> 사이클이 있으면, 자신에서 나가는 간선과 들어오는 간선이 있다. 사이클이 없으면 단순히 나가는 간선만 있다. 그렇기에, 자신으로 돌아오는 사이클을 만들지 않는 간선은 단절선이다. 한 컴포넌트가 떨어져 나가기 때문.
그러나, 사이클이 있으면, 자신으로 들어오는 간선이 있으므로, 끊어도 컴포넌트는 떨어져 나가지 않는다. 그렇기에, 단절선이 아니다. 즉, 사이클이 1개 이하인지 판단하기 위해서는 단순히 단절선이 아닌, 각 정점에 연결된 간선의 개수가 2개 이하이면(in deg, out deg)된다. 아래는 소스 코드이다.
#include<bits/stdc++.h>
#define INF 100001
using namespace std;
int dfsn[INF], V, E, cnt;
vector<int> a[INF];
vector<pair<int, int>> v;
map<pair<int, int>, int> m;
int DFS(int now, int par=0){
dfsn[now]=++cnt;
int res=dfsn[now];
for(int i=0;i<a[now].size();i++){
if(a[now][i]==par) continue;
if(dfsn[a[now][i]]>0) res=min(res, dfsn[a[now][i]]);
else{
int tmp=DFS(a[now][i], now);
res=min(res, tmp);
if(dfsn[now]<tmp){
int piv=now;
int piv2=a[now][i];
m[{now, a[now][i]}]=1;
m[{a[now][i], now}]=1;
}
}
}
return res;
}
int main(){
cin >> V >> E;
for(int i=0;i<E;i++){
int b, c;
cin >> b >> c;
a[b].push_back(c);
a[c].push_back(b);
}
for(int i=1;i<=V;i++){
if(!dfsn[i]) DFS(i);
}
for(int i=1;i<=V;i++){
int cnt=0;
for(int j=0;j<a[i].size();j++){
if(m.find({i, a[i][j]})==m.end()) cnt++;
}
if(cnt>2){
cout << "Not cactus";
return 0;
}
}
cout << "Cactus";
}
처음에는 단절점만 검사하려 했다. 그러나, 반례를 발견했다. 그것은 바로....
이 경우 2, 4는 단절점이 아니라서 검사 대상이 아니지만(잘못된 코드에서), 이 그래프는 Cactus가 아니다.
그리고 사실 앞서 말한 최대 2만 곱해지는 이유 때문에 굳?이 이렇게 골라서 계산할 필요도 없다는 거. 시간은 널널하다.
근데 이거 선인장 정의가 맞냐?
알아보니, 이건 "정점 선인장"의 정의고, "간선 선인장"도 있다 한다(BOJ 2111).
이것에 대한 판별은 BOJ 2111을 풀면 올린다.