[백준] 10891 Cactus? Not cactus? -선인장그래프

문제

선인장이란 양방향 그래프의 일종인데, 각 정점에 대해 자기 자신으로 돌아오는 경로(단순 사이클)가 하나 이하인 그래프이다. 주어진 그래프가 선인장일까? 아닐까?

입력

첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다.

다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정수 x,y (1 ≤ x,y ≤ N,x ≠ y)가 공백으로 구분되어 주어진다. 주어진 간선은 중복되지 않으며, 임의의 두 정점에 대해 경로가 존재한다.

출력

주어진 그래프가 선인장이면 "Cactus" 를 아니라면 "Not cactus" 를 출력한다.

 

선인장 그래프 문제입니다.

단순 사이클이란 한 사이클에서 같은 정점을 방문하지 않는 사이클입니다.

 

BCC로 간선을 묶으면 쉽게 해결할 수 있습니다.

1.

두개 이상의 BCC에 한 정점이 겹치게 된다면 이 그래프는 선인장이 아닙니다.

  그 정점에서 사이클이 두개 이상 생기기 때문입니다.

 

2.

만약 한 BCC안에 정점이 두개만 존재하면, 선인장입니다. 

그러나

만약 한 BCC안에 정점이 세개 이상일때, 간선의 개수가 정점의 개수보다 많다면,

그 BCC안에서는 단순사이클이 두개이상 생길 수 있습니다.

따라서 한 BCC안에는 정점의 개수와 간선의 개수가 같아야 합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int V, E, dfsn[100001], cnt;
stack<pi>st;
vi adj[100001];
vvi bcc;
vector<pi>bc;
//pre는 부모노드를 의미합니다.
int dfs(int k, int pre = -1) {

	//result는 도달가능한 정점의 최소 dfsn을 저장합니다.
	int result = dfsn[k] = ++cnt;

	//모든 도달가능한 정점에대해
	for (int next : adj[k]) {

		//부모노드라면 생략
		if (next == pre)continue;

		//만약 처음 방문하는 간선이라면 stack에 Push
		if (dfsn[k] > dfsn[next])st.push(pi{ k,next });

		//이미 방문한 정점이라면, dfsn값을 비교하여 result에 작은값을 저장합니다
		if (dfsn[next] > 0)result = min(result, dfsn[next]);

		//처음 방문한 정점이라면 dfs로 진행합니다
		else {

			//result와 자식정점의 dfsn와 비교해 작은값을 저장합니다.
			int temp = dfs(next, k);
			result = min(result, temp);

			//만약 현재 dfsn과 자식 dfsn을 비교했을때, 현재값이 크거나 같으면
			//현재노드의 부모노드로는 더이상 갈 수 없음을 의미합니다. BCC를 발견했습니다.
			//현재노드까지 BCC입니다.
			if (temp >= dfsn[k]) {

				vi vt;
				while (!st.empty()) {
					pi top = st.top();
					st.pop();
					vt.push_back(top.first);
					vt.push_back(top.second);
					if (top == pi{ k,next })break;
				}
				bcc.push_back(vt);
			}
		}
	}
	return result;
}
int main() {
	FAST;
	cin >> V >> E;
	rep(i, E) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	REP(i, V) {
		if (!dfsn[i])dfs(i);
	}
	int v[100001];
	mset(v);
    //모든 bcc에 대해서
	for (auto r : bcc) { 
    	//간선의 수
		int edges = r.size() / 2;
		sort(r.begin(), r.end());
		r.erase(unique(r.begin(), r.end()), r.end());
		if (r.size() > 2) {
        //간선이 2개를 초과할때, 정점의 개수와 다르다면 선인장이 아닙니다.
			if (edges != r.size()) { cout << "Not cactus"; return 0; }
			for (int c : r) {
				if (!v[c])v[c] = 1;
                //두개 이상의 bcc에 한 정점이 겹치면 선인장이 아닙니다.
				else {
					cout << "Not cactus";
					return 0;
				}
			}
		}
	}
    //선인장입니다.
	cout << "Cactus";
}

선인장 그래프