📝 문제 정보#
🧐 관찰 및 접근#
무향 그래프 $G = (V, E)$가 주어진다.
여기서 두가지 쿼리가 주어진다.
- 간선 $e \in E$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정
- 정점 $v \in V$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정
- 각각 살펴보자.
먼저, 문제조건에 의해 컴포넌트는 하나이므로 A, B는 기본적으로 연결되어있다고 판단하자.
간선 $e$를 없애는 경우
- 간선 $e$가 단절선이 아니라면, $A, B$의 연결성은 유지된다.
- 간선 $e$가 단절선이라면, $A, B$가 서로 다른 분리된 컴포넌트에 있을 때 분리된다.
- ![[Drawing 2026-01-29 09.30.57.excalidraw.png]]
- 위와 같이 DFS트리로 그래프를 해석해보자.
- 검은 간선은 tree edge
- 초록색 간선은 back edge
- 빨간색 간선은 자를 간선이다.
- 자를 간선이 단절선이라면, 잘라진 컴포넌트는 해당 단절선의 자식의 서브트리와 그 나머지 트리로 분리된다.
- 따라서, $A, B$ 모두가 서브트리 안에 있거나 서브트리 밖에 있다면 no, 그렇지 않다면 yes를 출력하면 된다.
- 이는 ETT로 계산하자.
- 따라서, $A, B$ 모두가 서브트리 안에 있거나 서브트리 밖에 있다면 no, 그렇지 않다면 yes를 출력하면 된다.
정점 $v$를 없애는 경우
- 정점 $v$가 단절점이 아니라면 $A, B$의 연결성은 유지된다.
- 정점 $v$가 단절점이라면, $A, B$가 서로 다른 분리된 컴포넌트에 있을 때 분리된다.
- 위처럼 DFS Tree로 해석할때, 이번에는 컴포넌트가 두개가 아닌 여러개로 분리될 수 있다.
- LCA처럼 binary lifting을 통해 $A, B$를 $C$의 자식 노드중 가장 높은곳으로 끌어올려보고, $G$의 $low$값을 비교해보자.
예제 입력 1의 DFS Tree ![[Drawing 2026-01-29 09.41.01.excalidraw.png]]
💻 풀이#
- 코드 (C++):
void solve(){
int N, E; cin >> N >> E;
UndirectedGraph G(N);
rep(i, 0, E){
int u, v; cin >> u >> v;
u--; v--;
G.add_edge(u, v);
}
G.dfs();
rep(i, 0, N) rep(j, 0, 20) par[i][j] = -1;
rep(i, 0, N) par[i][0] = G.par[i];
rep(j, 1, 20) rep(i, 0, N) if(par[i][j-1] != -1) par[i][j] = par[par[i][j-1]][j-1];
int Q; cin >> Q;
while(Q--){
int op; cin >> op;
if(op == 1){
int A, B, G1, G2; cin >> A >> B >> G1 >> G2;
A--; B--; G1--; G2--;
if(G.depth[G1] > G.depth[G2]) swap(G1, G2);
if(!G.isBridge[G2] || G.par[G2] != G1){
cout << "yes\n";
continue;
}
bool AinTree = (G.discoverTime[G2] <= G.discoverTime[A] && G.discoverTime[A] <= G.ettOut[G2]);
bool BinTree = (G.discoverTime[G2] <= G.discoverTime[B] && G.discoverTime[B] <= G.ettOut[G2]);
if(AinTree ^ BinTree) cout << "no\n";
else cout << "yes\n";
}
else{
int A, B, C; cin >> A >> B >> C;
A--; B--; C--;
if(!G.isArticulation[C]){
cout << "yes\n";
continue;
}
int Aid = get_low(C, A, G);
int Bid = get_low(C, B, G);
if(Aid == Bid) cout << "yes\n";
else cout << "no\n";
}
}
}