(BOJ) 3830 교수님은 기다리지 않는다

문제: https://www.acmicpc.net/problem/3830

 

 

문제 풀이:

1. 입력 받은 샘플에 상대적인 무게를 지정해준다. (그룹별로)

2. 두 그룹이 합쳐지는 경우 사이즈가 작은 그룹을 큰 그룹에 포함되도록 만든다

   큰 그룹의 끝에서 작은 그룹으로 dfs를 돌려서 큰 그룹의 번호와 큰 그룹의 상대적인 무게에 맞는 무게를 부여

 

이미 존재하는 그룹에 새로 연결하는 경우는 그냥 상수시간으로 해결 가능하고,

두 그룹 묶을 때, 작은 그룹만 dfs 돌리니까 최악의 연산은 전체 dfs 한 번 돌리는 정도가 된다. 

 

* 주의:

무게 저장할 때, long long 써야하는데, 이것만 long long으로 하는 것이 아니라 이 것과 관련된 변수들도 다 long long으로 해줘야 한다.

 

 

 

소스 코드:

typedef pair<int, long long> P;
int n, m,g[100001],cnt;
long long cost[100001];
bool visit[100001];
vector<vector<P>> adj;
vector<vector<int>> groupN;

void dfs(int start,int num) {
	visit[start] = true;
	for (auto i : adj[start]) {
		if (visit[i.first]) continue;
		cost[i.first] = cost[start] + i.second;
		g[i.first] = num;
		groupN[num].push_back(i.first);
		dfs(i.first, num);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (1) {
		cin >> n >> m;
		if (n == 0) break;
		memset(visit, false, sizeof(visit));
		adj.clear();
		adj.resize(n + 1);
		groupN.clear();
		cnt = 1;
		for (int i = 0; i < m; i++) {
			char c;
			cin >> c;
			if (c == '!') {
				int q, e;
				long long w;
				cin >> q >> e >> w;
				adj[q].push_back({ e,w });
				adj[e].push_back({ q, -w });
				if (visit[q] && !visit[e]) {
					cost[e] = cost[q] + w;
					g[e] = g[q];
					groupN[g[q]].push_back(e);
				}
				else if (!visit[q] && visit[e]) {
					cost[q] = cost[e] - w;
					g[q] = g[e];
					groupN[g[e]].push_back(q);
				}
				else if (!visit[q] && !visit[e]) {
					groupN.resize(++cnt);
					cost[q] = 0;
					cost[e] = w;

					g[q] = g[e] = cnt - 1;
					groupN[cnt - 1].push_back(q);
					groupN[cnt - 1].push_back(e);
				}
				else if (g[q] == g[e]) continue;
				else {
					if (groupN[g[q]].size() < groupN[g[e]].size()) {
						for (auto i : groupN[g[q]]) {
							visit[i] = false;
						}
						groupN[g[q]].clear();
						dfs(e, g[e]);
					}
					else {
						for (auto i : groupN[g[e]]) {
							visit[i] = false;
						}
						groupN[g[e]].clear();
						dfs(q, g[q]);
					}
				}
				visit[q] = true;
				visit[e] = true;
			}
			else {
				int q, w;
				cin >> q >> w;
				if (visit[q] && visit[w] && g[q] == g[w]) {
					cout << cost[w] - cost[q]<<'\n';
				}
				else cout << "UNKNOWN\n";
			}
		}
		
	}
	return 0;
}