Articulation

📝 문제 정보 # 링크: 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"; } } 🔒 구현 코드 잠금