[백준 2406] 안정적인 네트워크

분류 : 최소 스패닝 트리

 

요구사항

n-2개의 연결으로 최소 스패닝 트리 만들기

 

풀이

1번은 연결되어 있으니, vertex가 n-2가 되어있으면 모두 연결되어 있는것이다

아래는 힙으로 짠 코드인데 vector로 정렬한뒤 사용하면 더 빠를것같다

 

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
struct go {
	int dist;
	int x;
	int y;
};
struct comp {
	bool operator()(go  a, go b) {
		if (a.dist > b.dist) return true;
		return false;
	}
};
int map[1100][1100];
int parent[1100];
int Find(int x) {
	if (parent[x] == x) return x;
	else return x = Find(parent[x]);
}
bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return false;
	if (x != y) {
		parent[x] = y;
		return true;
	}

}
int n, m;
priority_queue<go, vector<go>, comp> q;
int main() {
	scanf("%d%d", &n, &m);
	int flag = 0;
	int vertex = 0;
	for (int i = 1; i <= n; i++) parent[i] = i;
	//for (int i = 1; i <= n; i++) Union(1, i);
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (Find(x) != Find(y)) {
			Union(x, y);
			vertex++;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);
			if (i == j) continue;
			if (i == 1 || j == 1) continue;
			
			//이미 같은거라면
			int parenti = Find(i);
			int parentj = Find(j);
			//부모가 같지 않다 연결되지 않은거라면 q에 넣는다
			if (parenti != parentj) {
				q.push({ map[i][j],i,j });
			//	cout << "A" << endl;
			}
		}
	}
	//cout << "A" << endl;
	vector<go> v;
	long long ans=0;
	while (!q.empty()) {
	//	cout << "B" << vertex<<endl;
		int nowr = q.top().x;
		int nowc = q.top().y;
		int dist = q.top().dist;
		q.pop();
		if (Find(nowr) != Find(nowc)) {
			//cout << "!" << endl;
			Union(nowr, nowc);
			v.push_back({ 0,nowr,nowc });
			ans += dist;
			vertex++;
		}
		if (vertex == n - 2)
			break;
	}
	//cout << "!" << endl;
	cout << ans << " " << v.size() << endl;
	if (v.size() == 0) {
		printf("0\n");
	}
	else {
		for (int i = 0; i < v.size(); i++) {
			printf("%d %d\n", v[i].x, v[i].y);
		}
	}
}