[ boj : 2406] 안정적인 네트워크

www.acmicpc.net/problem/2406

2406번: 안정적인 네트워크

문제 : 1번 노드는 모든 노드와 연결이 되어있고, 나머지 노드들간 관계가 주어진다. 이때 어떤 한 노드를 제거하더라도 모든 노드가 연결되어 있는 상태가 되도록 간선을 연결해라

 

해설 : 어떤 한 노드를 삭제했을때 모든 노드가 연결되게끔 해주면 되니, 한 노드를 하나씩 삭제해보고 mst를 만들면 되겠죠. 처음에 이렇게 풀었습니다. 그러나 시간이 어마어마하게 나오더라구요;;; 아마 삭제하고 다시 벡터에 복사하는 과정이 오래걸리는 것 같습니다.

 

그래서 이를 단축해 보고자, 다시 생각해보았습니다. 결국 1번 노드는 모든 노드들과 연결이 되어있는 상태이니 1번을 제외한 한 노드를 제거하더라도 무조건 안정적인 네트워크가 유지가 됩니다. 그러면 1번 노드를 제거했을때만 생각하면 되겠죠. 마찮가지입니다. 1번노드를 제거했을때 모든 노드들이 연결이 되도록 만들기 위해선 하나씩 간선을 추가해 보면서 연결이 되는지를 체크해 보면 됩니다. 역시나 mst 입니다.

 

#include<bits/stdc++.h>

using namespace std;

struct info {
	int x, y, w;
	bool operator<(const info& cur)const {
		return w < cur.w;
	}
};

int n, m, x, y;
int parent[1001];
int board[1001][1001];
vector<int> v[1001];
vector<info> edge;

int sum = 0;
vector<pair<int, int>> ans;

void solve();
bool check_union(int x, int y);
void union_parent(int x, int y);
int get_parent(int x);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
}
void solve()
{		
	cin >> n >> m;
	for (int i = 1; i <= n; i++)parent[i] = i;
	for (int i = 2; i <= n; i++) 
		v[1].push_back(i);
	
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
		union_parent(x, y);
	}
	vector<info> edge;	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> board[i][j];
			if (i == 1 || j == 1)continue;
			if (i < j && !check_union(i, j))
				edge.push_back({ i,j,board[i][j] });
		}	
	sort(edge.begin(), edge.end());	
	for (info u : edge) {
		if (!check_union(u.x, u.y)) {
			sum += u.w;
			ans.push_back({ u.x, u.y });
			union_parent(u.x, u.y);
		}
	}
	cout << sum << " " << ans.size() << "\n";
	for (pair<int, int> p : ans)
		cout << p.first << " " << p.second << "\n";
}
bool check_union(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);

	if (x != y)return false;
	return true;
}
void union_parent(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);

	parent[y] = x;
}
int get_parent(int x)
{
	if (x == parent[x])return x;
	return parent[x] = get_parent(parent[x]);
}