https://www.acmicpc.net/problem/11266
단절점을 구하는 문제이다.

단절점이란?

무향 연결 그래프에서 하나의 정점을 지웠을 때 (연결된 간선들도 제거),
두 개의 연결 그래프로 나눠진다면 → 단절점
즉, 그 정점 없이는 다른 정점을 한번에 방문할 수 없다는 것

단절점 판별

어떤 정점 A에 연결된 모든 정점들 중,
두 정점들 간에 정점 A를 거치지 않고 갈 수 있는 우회경로가 존재하지 않는 경우
출처 : https://jason9319.tistory.com/119

어떤 정점 A와 A에 연결된 정점 B에 대해

1. A가 시작정점이 아닌 경우
    정점 A보다 방문순서가 늦은 정점들에 대해
    해당 정점에서, A보다 먼저 탐색되는 정점으로 가는 경로가 없다면 → 단절점

2. A가 시작정점인 경우
    A의 자식이 2개 이상 → 단절점

단절점 판별은 DFS안에서 해결이 가능하다

단절점 소스코드

구현은 소스코드에서 확인 가능

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N_ = 10001;
int V,E,order;
vector<int> v[N_];
int visited[N_]; //order 저장 
bool ans[N_];

int dfs(int cur, bool root){
	visited[cur] = ++order;
	int ret = visited[cur];
	
	int child = 0;
	
	for(int next : v[cur]){
		if(!visited[next]){ //방문한 적 없음, 자식임 
			child++;
			int low = dfs(next, false);
			if(!root && low>=visited[cur]) ans[cur] = true;
			ret = min(ret, low); 
		}
		else{ //방문한 적 있음  
			ret = min(ret, visited[next]);
		}
	}
	if(root && child>=2){ //시작정점이고, 자식이 2개 이상
		ans[cur] = true;
	}
	return ret;
}

int main(){
	fastio
	
	cin>>V>>E;
	for(int i = 0; i<E; i++){
		int a,b; cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	for(int i = 1; i<=V; i++){
		if(!visited[i]) dfs(i,1); //문제조건 : 입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다
	}
	
    //답안출력
	int cnt = 0;
	vector<int> ansList;
	for(int i = 1; i<=V; i++){
		if(ans[i]){
			cnt++;
			ansList.push_back(i);
		}
	}
	cout<<cnt<<"\n";
	for(int i = 0; i<ansList.size(); i++){
		cout<<ansList[i]<<" ";
	}
}

제출결과

그렇다면 이번엔 단절선이다
https://www.acmicpc.net/problem/11400

단절선이란?

간선을 제거했을 때 그래프가 여러가지로 나눠지는 것

단절선 판별

현재 정점의 방문 순서가 아직 방문하지 않은 자식 정점의 순서보다 빨라,
현재 간선을 거치지 않고서는 순서가 빠른 모든 정점에 도달할 수 없다면
현재 간선은 단절선이 된다.
출처 : https://littlesam95.tistory.com/175

단절점과 다른점?

• 부모 정점은 발견 시간 갱신 대상이 아니다.
• low >= discovered[now]에서 =이 빠진다.
• 루트 노드의 단절선을 자식의 수로 판별하지 않는다.

출처 : https://ip99202.github.io/posts/단절선-알고리즘/

단절선 소스코드

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>

const int N_ = 100001;
int V,E,order;
vector<int> v[N_];
int visited[N_]; //order 저장 
vector<pii> ans;

int dfs(int cur, int parent){
	visited[cur] = ++order;
	int ret = visited[cur];
	
	for(int next : v[cur]){
		
		if(next == parent) continue; //부모정점으로 가는 간선 제외 
		
		if(!visited[next]){ //방문한 적 없음, 자식임 
			int low = dfs(next, cur);
			ret = min(ret, low);
			if(low>visited[cur]) {
				ans.push_back({min(cur,next),max(cur,next)});	
			}
		}
		else{ //방문한 적 있음  
			ret = min(ret, visited[next]);
		}
	}
	return ret;
}

int main(){
	fastio
	
	cin>>V>>E;
	for(int i = 0; i<E; i++){
		int a,b; cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	dfs(1,0);
	
	//답안출력 
	sort(ans.begin(),ans.end());
	int size = ans.size();
	cout<<size<<"\n";
	for(int i = 0; i<size; i++){
		cout<<ans[i].first<<" "<<ans[i].second<<"\n";
	}
}

제출결과

N범위를 잘못 본 나의 실수^.~