백준 BOJ 1922 - 네트워크 연결

얘도 여름학교에서 어제 배운 따끈따끈한 문제

유니온파인드 + a를 통해 해결해줄 수 있다.

나름 구조체도 만들고 비교함수도 짜고

할게 좀 많았다 ㅎㅎ

​

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

소스코드는 이거.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <deque>
 
using namespace std;

struct line{ int S, E, W; };

bool compare(line a, line b){ return a.W < b.W; }

vector<line> graph;
int parent[200001] = {0};

int find(int k){
	if(parent[k] == k) return k;
	return parent[k] = find(parent[k]); 
}

void union_f(int a, int b){
	int va = find(a);
	int vb = find(b);
	if(va!=vb) parent[va] = vb;
	return;
}

int main(){
	line l1, l2;
	int n,m,a,b,c;
	long long int sum = 0;
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		scanf("%d %d %d", &a, &b, &c);
		l1.S = a; l1.E = b; l1.W = c;
		graph.push_back(l1);
	}
	
	sort(graph.begin(), graph.end(), compare);
	for(int i=0; i<200001; i++) parent[i] = i;
	
	for(int i=0; i<graph.size(); i++){
		if(!(find(graph[i].S) == find(graph[i].E))){
			sum += graph[i].W;
			union_f(graph[i].S, graph[i].E);
		}
	}
	printf("%lld", sum);
	return 0;
}

무난하게 AC 받을 수 있었다

사실 여름학교 문제들 테스트케이스가 어마어마하게 빡세서

여름학교에서 푼 문제들은 왠만해서는 틀릴거 같지 않다 ㅋㅋㅋ

​