<백준> 11400번 단절선, 이중 연결 요소.

[https://www.acmicpc.net/problem/11400]

 

음 내가 생각한 풀이는

 

단절선은 

 

단절점 - 단절점

단절점 - 혼자인 노드 (방금 단절점이랑만 연결된 노드인거) 라고 생각하고 했는데 틀렸다.;;

 

#define _CRT_SECURE_NO_WARNINGS
#define NUM 100002
#include<utility>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<pair<int, int>> edges;
vector<int> adj[NUM];
int order[NUM];
int arti[NUM];
int root = 1;
//이게 첨에 1부터 되야지,,order를 0으로 초기화했잔아...
int number = 0;

int dfs(int u) {
	//prev는 해당 노드 이후로 가장 작은 순서
	//ret는 현재 노드와 prev중 더 작은거.
	int ret,prev,child=0;
	//order[u]에 값도 잘못넣음, depth로 넣었었따;;
	order[u] = ++number;
	ret = order[u];

	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];

		//v는 방문 했었음.갈필요 없네.
		if (order[v] != 0) {
			//여기도 order[v]대신 order[u]로 했었다.
			ret = ret < order[v] ? ret : order[v];
			continue;
		}

		//v는 아직 방문하지 않음.
		prev = dfs(v);
		child++;

		//여기서 틀림,order[u] 대신 ret씀
		if (root != u && prev >= order[u]) {
			arti[u] = 1;
		}

		ret = prev < ret ? prev : ret;
	}

	if (root == u) {
		arti[u] = (child >= 2);
	}

	return ret;
}
int N, M;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a,b;
		cin >> a >>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		edges.push_back(make_pair(a, b));
	}

	//이걸 왜 모든 노드를 루트로 하지?
	//이래야 단절된 지점들에 대해 가능할듯.
	for (int i = 1; i <= N; i++) {
		if (!order[i]) {
			root = i;
			dfs(i);
		}
	}
	int cnt = 0;
	for (int i = 0; i < M; i++) {
		int a, b;
		a = edges[i].first;
		b = edges[i].second;

		if (arti[a] && arti[b]) {
			cnt++;
		}
		else if (arti[a] == 1 && adj[b].size() == 1) {
			cnt++;
		}
		else if (arti[b] == 1 && adj[a].size() == 1) {
			cnt++;
		}
	}
	cout << cnt << "\n";
	for (int i = 0; i < M; i++) {
		int a, b;
		a = edges[i].first;
		b = edges[i].second;

		if (b < a) {
			int tmp = a;
			a = b;
			b = tmp;
		}

		if (arti[a] && arti[b]) {
			cout << a << " " << b << "\n";
		}
		else if (arti[a] == 1 && adj[b].size() == 1) {
			cout << a << " " << b << "\n";
		}
		else if (arti[b] == 1 && adj[a].size() == 1) {
			cout << a << " " << b << "\n";
		}
	}

	return 0;
}

 

 

 

---

일단 이중 연결 요소에 관해 공부하자. BCC

[https://makemethink.tistory.com/148] 자료는 제일 자세한거 같은데, 잘 이해가 안된다;; 음 일단