[백준] 6672 Electricity

문제

Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there is not enough power in one area, while there is a large surplus in the rest of the country.

ACM++ has therefore decided to connect the networks of some of the plants together. At least in the first stage, there is no need to connect all plants to a single network, but on the other hand it may pay up to create redundant connections on critical places - i.e. the network may contain cycles. Various plans for the connections were proposed, and the complicated phase of evaluation of them has begun.

One of the criteria that has to be taken into account is the reliability of the created network. To evaluate it, we assume that the worst event that can happen is a malfunction in one of the joining points at the power plants, which might cause the network to split into several parts. While each of these parts could still work, each of them would have to cope with the problems, so it is essential to minimize the number of parts into which the network will split due to removal of one of the joining points.

Your task is to write a software that would help evaluating this risk. Your program is given a description of the network, and it should determine the maximum number of non-connected parts from that the network may consist after removal of one of the joining points (not counting the removed joining point itself).

입력

The input consists of several instances.

The first line of each instance contains two integers 1 <= P <= 10 000 and C >= 0 separated by a single space. P is the number of power plants. The power plants have assigned integers between 0 and P - 1. C is the number of connections. The following C lines of the instance describe the connections. Each of the lines contains two integers 0 <= p1, p2 < P separated by a single space, meaning that plants with numbers p1 and p2 are connected. Each connection is described exactly once and there is at most one connection between every two plants.

The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.

출력

The output consists of several lines. The i-th line of the output corresponds to the i-th input instance. Each line of the output consists of a single integer C. C is the maximum number of the connected parts of the network that can be obtained by removing one of the joining points at power plants in the instance.

 

그래프의 한 정점을 지웠을때 가장많이 만들 수 있는 그래프의 개수를 묻는 문제입니다.

그래프의 간선을 BCC로 묶고, 해당하는 정점을 정리했을때, 가장 많은 BCC에 걸치는 정점을 지운다면 그 개수만큼 그래프가 늘어나게됩니다.

따라서 기존 그래프의 개수 + 최대 겹치는 개수 - 1 이 정답입니다.

 

#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;
	while (cin >> V >> E) {
		if (V == 0 && E == 0)break;
		rep(i, V)adj[i].clear();
		mset(dfsn);
		cnt = 0;
		int num = 0;
		bcc.clear();
		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]) num++,dfs(i);
		}
		int v[10001];
		mset(v);
		for (auto r : bcc) {
			sort(r.begin(), r.end());
			r.erase(unique(r.begin(), r.end()), r.end());
			for (auto c : r) {
				v[c]++;
			}
		}
		cout << num + *max_element(v, v + V) - 1 << "\n";
	}
}