[백준 6672] Electricity

문제 링크 => 6672번: Electricity (acmicpc.net)

6672번: Electricity

---

BCC(Biconnected Component) 문제이다.

 

연결된 노드들 사이에서 임의의 노드를 하나 제거할 때, 연결된 수의 최댓값을 묻는 문제이다.

 

처음에 연결된 노드들이 한번에 연결된 경우가 아닌 끼리끼리 연결된 경우가 문제의 예시로 주어져서 이 경우를 생각해봤다.

 

즉, 모든 노드들이 연결된 경우라면 현재 노드에 대한 BCC의 갯수를 반환하면 그만이지만 따로 따로 연결된 경우는 다르다.

 

따라서 이 경우를 해결하기 위해서 DFS Tree를 만드는 과정에서 각 Tree 별로 몇 개로 구성되는지를 알도록 했다.

 

DFS Tree 의 갯수를 connected_Cnt 라고 한다면 답은 각 노드 별로 connected_Cnt - 1 + (현재 노드에 대한 BCC 갯수) 값 중에 최댓값이 된다.

 

풀이 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[10001];
vector<pair<int, int>> BCC[10001];
int low[10001], dfn[10001], child[10001], result[10001];
int V, E, nodeNum, bccNum, connected_Cnt;
stack<pair<int, int>> S;

void initialize() {
	connected_Cnt = nodeNum = 0;

	for (int i = 0; i < V; i++) {
		v[i].clear();
		result[i] = child[i] = low[i] = dfn[i] = 0;
		
	}

	for (int i = 1; i <= bccNum; i++) {
		BCC[i].clear();
	}

	bccNum = 0;
}

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

	return 1;
}

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

	for (int y : v[x]) {
		if (y == mp) continue; 
		if (!dfn[y]) { 
			child[x]++;
			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]) { 
			low[x] = min(low[x], dfn[y]);
			S.push({ x,y });
		}
	}
}

void solve() {

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

	for (int i = 1; i <= bccNum; i++) {
		map<int, int> m;
		for (int j = 0; j < BCC[i].size(); j++) {
			int x = BCC[i][j].first, y = BCC[i][j].second;
			if (!m[x]) {
				result[x]++;
				m[x] = 1;
			}
			if (!m[y]) {
				result[y]++;
				m[y] = 1;
			}
		}
	}

	int maxRes = 0;
	for (int i = 0; i < V; i++) {
		maxRes = max(maxRes, result[i] + connected_Cnt - 1);
	}

	cout << maxRes << endl;
}

int main() {

	while (input()) {
		solve();
		initialize();
	}

	return 0;
}