[백준 10891] Cactus? Not cactus?

문제 링크 => 10891번: Cactus? Not cactus? (acmicpc.net)

10891번: Cactus? Not cactus?

---

BCC를 이용한 문제이다.

 

Cactus 임을 판단하기 위해서 두 개의 조건을 만족해야 한다.

 

1. BCC로 묶인 간선의 갯수가 3개 이상인 경우 BCC로 묶여 있는 정점들의 갯수와 동일한지 파악해야 한다.

 

2. 1번 조건을 고려할 때, 간선의 갯수가 3개 이상으로 묶인 BCC 중에서 임의의 정점이 2개 이상인 경우 즉, 임의의 정점을 기준으로 간선의 갯수가 3개 이상으로 묶인 BCC가 여러개 만들어 지는 경우를 제외해야 한다. (예제를 통해서 정확하게 알아보도록 한다)

 

1번 조건과 2번 조건을 모두 만족하는 경우 주어진 그래프는 Cactus 이다.

 

먼저 문제에서 주어진 예제를 보도록 한다.

---

[예제 1] 에 대한 그래프이다.

 

다음 그래프에서 BCC는 [ (1, 2), (2, 3), (3, 1) ] , [ (3, 4) ] 으로 묶여진다.

 

Cactus 임을 판단하기 위해서 2조건을 만족해야 한다.

 

1번 조건으로 간선이 3개 이상인 경우는 딱 한 가지 밖에 없다. ( 간선이 3개 미만은 고려하지 않음 )

 

[ (1, 2), (2, 3), (3, 1) ] => 정점 1, 2, 3 으로 3개로 BCC로 묶인 간선의 갯수(3)와 BCC로 묶인 정점의 갯수(3)가 동일하므로 해당 그래프는 Cactus 이다.

 

 

[예제 2] 에 대한 그래프이다.

 

다음 그래프에서 BCC는 [ (1, 2), (2, 3), (3, 1) ] , [ (3, 4), (4, 5), (5, 3) ] 으로 묶여진다.

 

1번 조건만 본다면 간선의 갯수가 3개 이상인 경우는 두 가지 이고 간선의 갯수 3개, 정점의 갯수 3개 이므로 동일하기 때문에 1번 조건은 만족한다.

 

2번 조건을 고려한다면 3번 정점을 기준으로 간선이 3개로 묶인 BCC 가 2개 있다. 

 

따라서 이 그래프는 Not cactus 이다.

 

그렇다면 위의 그래프가 Cactus 이려면 다음과 같은 그래프가 되어야 한다. (정점 6을 추가)

 

 

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> v[100001];
vector<pair<int, int>> BCC[100001];
int low[100001], dfn[100001], child[100001];
int V, E, nodeNum, bccNum;
stack<pair<int, int>> S;

void input() {
	cin >> V >> E;
	
	for (int i = 0; i < E; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

void dfs(int x, int mp = -1) {
	dfn[x] = low[x] = ++nodeNum;

	for (auto y : v[x]) {
		if (y == mp) continue;
		if (!dfn[y]) {
			S.push({ x,y });
			dfs(y, x);
			low[x] = min(low[x], low[y]);
			if (dfn[x] <= low[y]) {
				bccNum++;
				pair<int, int> P = { x,y };
				while (S.top() != P) {
					BCC[bccNum].push_back(S.top());
					S.pop();
				}
				BCC[bccNum].push_back(S.top());
				S.pop();
			}
		}
		else if (dfn[x] > dfn[y]) {
			S.push({ x,y });
			low[x] = min(low[x], dfn[y]);
		}
	}
}

void solve() {

	for (int i = 1; i <= V; i++) {
		if (!dfn[i]) dfs(i);
	}

	map<int, int> m;
	for (int i = 1; i <= bccNum; i++) {
		if (BCC[i].size() >= 3) {
			int cnt = 0;
			for (int j = 0; j < BCC[i].size(); j++) {
				int x = BCC[i][j].first, y = BCC[i][j].second;
				if (!m[x]) {
					m[x] = 1;
					cnt++;
				}
				if (!m[y]) {
					m[y] = 1;
					cnt++;
				}
			}
			if (cnt != BCC[i].size()) {
				cout << "Not cactus";
				return;
			}
		}
	}

	cout << "Cactus";
	return;
}

int main() {

	input();
	solve();

	return 0;
}