Bridge

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1734 🧐 관찰 및 접근 # 무향 그래프 $G = (V, E)$가 주어진다. 여기서 두가지 쿼리가 주어진다. 간선 $e \in E$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 정점 $v \in V$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 각각 살펴보자. 먼저, 문제조건에 의해 컴포넌트는 하나이므로 A, B는 기본적으로 연결되어있다고 판단하자.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14675 🧐 관찰 및 접근 # 트리에서의 단절점과 단절선을 생각해보자. 트리에서 모든 간선은 단절선이다. 사이클 없는 연결 그래프니까 트리에서 리프노드를 제외한 모든 노드는 단절점이다. 위와 이유가 같다. 우회경로로 쓸 back edge가 없다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } cin >> Q; while(Q--){ int t, k; cin >> t >> k; if(t == 1) cout << ((int)links[k].size() == 1 ? "no\n" : "yes\n"); else cout << "yes\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10891 🧐 관찰 및 접근 # 어떤 정점이 최대 한개의 사이클에만 속해있다면, 해당 그래프는 정점 선인장이다. $\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"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10891 🧐 관찰 및 접근 # 어떤 정점이 최대 한개의 사이클에만 속해있다면, 해당 그래프는 정점 선인장이다. $\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"; } 🔒 구현 코드 잠금