📝 문제 정보#
🧐 관찰 및 접근#
- 어떤 정점이 최대 한개의 사이클에만 속해있다면, 해당 그래프는 정점 선인장이다.
- $\text{DP}[i]$ : 정점 $i$의 부모와 정점 $i$의 자식을 잇는 tree edge가 아닌 간선의 수라고 정의하자.
- 어떤 그래프가 정점 선인장일 필요충분조건은 $\forall i$ 에 대해 $\text{DP}[i] \leq 1$인 것이다.
- 이는 DFS+누적합처럼 계산할 수 있다.
💻 풀이#
- 코드 (C++):
void dfs(int c, int p, int d){
depth[c] = d;
par[c] = p;
DP[c] = 0;
for(auto n: links[c]){
if(n == p) continue;
if(depth[n] == 0){
dfs(n, c, d+1);
DP[c] += DP[n];
}
else if(depth[n] < depth[c]) DP[c]++;
else DP[par[c]]--;
}
}
void solve(){
cin >> N >> M;
rep(i, 0, M){
int u, v; cin >> u >> v;
links[u].push_back(v);
links[v].push_back(u);
}
dfs(1, -1, 1);
bool isCactus = true;
rep(i, 1, N+1) if(DP[i] > 1) isCactus = false;
if(isCactus) cout << "Cactus";
else cout << "Not cactus";
}