글 읽기 - union-find로구현했는데 시간초과가납니다...

isvara 4년 전 1

초기상태부터 긴간선을 선택하면서 다른그룹이면 연결하면서 계산하도록 구현했고

union-find를 사용했는데 시간초과를 받았습니다. 5%정도에서 멈추내요 혹시.. 이거 왜이렇게 시간초과가 나는지 지적해주실수있으신가요??

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cstring>
#include<string.h>
using namespace std;

int check[100001];

struct disjoinset {
	vector<int>parent;
	disjoinset(int n) {
		parent.resize(n + 1);
		for (int i = 1; i <= n; i++)
		{
			parent[i] = i;
			check[i] = 1;
		}
	}
	int find(int u) {
		if (u == parent[u])
			return u;
		
		return find(parent[u]);
	}
	void merge(int u, int v) {
		parent[u] = v;
	}
};
int n,m;
int sum = 0;
int answer = 0;
vector<pair<int,pair<int, int>>>edge;

const int MOD = 100000000;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		edge.push_back({w,{x,y }});
		sum += w;
	}
	disjoinset group(n);
	

	sort(edge.begin(), edge.end(), greater<pair<int, pair<int, int>>>());

	for (int i = 0; i < edge.size(); i++)
	{
		int parent_u = group.find(edge[i].second.first);
		int parent_v = group.find(edge[i].second.second);
		int w = edge[i].first;
		

		if (parent_u != parent_v)
		{
			answer += ((check[parent_u] * check[parent_v]) *sum)%MOD;

			answer %= MOD;
			
			group.merge(parent_u,parent_v);

			check[parent_u] += check[parent_v];//집합 크기 증가
			check[parent_v] = check[parent_u];			
		}
		sum -= w;
	}
	cout << answer;
}

terrasphere 2년 전 0

제 생각에는 find 함수에서 경로 압축을 사용하지 않아서 시간초과가 난 것 같습니다. find를 할때마다 경로압축을 할 수 있게 return parent[u] = find(parent[u]); 로 바꾸면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

union-find로구현했는데 시간초과가납니다...

isvara 4년 전 1

terrasphere 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말