[C++] μœ λ‹ˆμ˜¨ νŒŒμΈλ“œ(Union-Find)

2020. 5. 1. 16:33Β·πŸ“ Computer Science/✏ Algorithm

μœ λ‹ˆμ˜¨ νŒŒμΈλ“œ(Union-Find)

  • μ„œλ‘œμ†ŒμΈ 집합듀을 λΆ„ν• ν•˜μ—¬ μ €μž₯ν•œ μ§‘ν•©
  • Union(): 두 μ§‘ν•©μ˜ 루트 λΆ€λͺ¨λ₯Ό ν•©μΉ¨
  • Find(): μžμ‹ μ˜ 루트 λΆ€λͺ¨λ₯Ό μ°Ύμ•„ κ³„μ†ν•΄μ„œ 거슬러 μ˜¬λΌκ°€λŠ” κ³Όμ •

 

μœ λ‹ˆμ˜¨ νŒŒμΈλ“œ

 

문제

 

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

 

1717번: μ§‘ν•©μ˜ ν‘œν˜„

첫째 쀄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 μ£Όμ–΄μ§„λ‹€. m은 μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” μ—°μ‚°μ˜ κ°œμˆ˜μ΄λ‹€. λ‹€μŒ m개의 μ€„μ—λŠ” 각각의 연산이 μ£Όμ–΄μ§„λ‹€. 합집합은 0 a b의 ν˜•νƒœλ‘œ μž…λ ₯이 μ£Όμ–΄μ§„λ‹€. μ΄λŠ” aκ°€ ν¬ν•¨λ˜μ–΄ μžˆλŠ” μ§‘ν•©κ³Ό, bκ°€ ν¬ν•¨λ˜μ–΄ μžˆλŠ” 집합을 ν•©μΉœλ‹€λŠ” μ˜λ―Έμ΄λ‹€. 두 μ›μ†Œκ°€ 같은 집합에 ν¬ν•¨λ˜μ–΄ μžˆλŠ”μ§€λ₯Ό ν™•μΈν•˜λŠ” 연산은 1 a b의 ν˜•νƒœλ‘œ μž…λ ₯이 μ£Όμ–΄μ§„λ‹€. μ΄λŠ” a와 bκ°€ 같은 집합에 ν¬ν•¨λ˜μ–΄ μžˆλŠ”μ§€λ₯Ό ν™•μΈν•˜λŠ” 연산이닀. a

www.acmicpc.net

#include <iostream>
using namespace std;

int parent[1000001];

int Find(int a)
{
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (b < a)
		parent[a] = b;
	else
		parent[b] = a;
}

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 0; i <= n; ++i)
		parent[i] = i;

	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;

		if (a == 0)
			Union(b, c);
		else {
			if (Find(b) == Find(c))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}
}

 

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

 

4195번: 친ꡬ λ„€νŠΈμ›Œν¬

문제 λ―Όν˜μ΄λŠ” μ†Œμ…œ λ„€νŠΈμ›Œν¬ μ‚¬μ΄νŠΈμ—μ„œ 친ꡬλ₯Ό λ§Œλ“œλŠ” 것을 μ’‹μ•„ν•˜λŠ” μΉœκ΅¬μ΄λ‹€. μš°ν‘œλ₯Ό λͺ¨μœΌλŠ” μ·¨λ―Έκ°€ μžˆλ“―μ΄, λ―Όν˜μ΄λŠ” μ†Œμ…œ λ„€νŠΈμ›Œν¬ μ‚¬μ΄νŠΈμ—μ„œ 친ꡬλ₯Ό λͺ¨μœΌλŠ” 것이 취미이닀. μ–΄λ–€ μ‚¬μ΄νŠΈμ˜ 친ꡬ 관계가 생긴 μˆœμ„œλŒ€λ‘œ μ£Όμ–΄μ‘Œμ„ λ•Œ, 두 μ‚¬λžŒμ˜ 친ꡬ λ„€νŠΈμ›Œν¬μ— λͺ‡ λͺ…이 μžˆλŠ”μ§€ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. 친ꡬ λ„€νŠΈμ›Œν¬λž€ 친ꡬ κ΄€κ³„λ§ŒμœΌλ‘œ 이동할 수 μžˆλŠ” 사이λ₯Ό λ§ν•œλ‹€. μž…λ ₯ 첫째 쀄에 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ κ°œμˆ˜κ°€ μ£Όμ–΄μ§„λ‹€. 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 첫째 μ€„μ—λŠ” 친ꡬ 관계

www.acmicpc.net

#include <iostream>
#include <map>
#include <string>
using namespace std;

map<string, int> m;
int parent[200001], cnt[200001];

int Find(int a) 
{
	if (a == parent[a]) 
		return a;
	return parent[a] = Find(parent[a]);
}

int Union(int a, int b) 
{
	a = Find(a);
	b = Find(b);

	if (a != b) {
		parent[b] = a;
		cnt[a] += cnt[b];
		cnt[b] = 1;
	}
	return cnt[a];
}

int main() 
{
	int T, F;
	cin >> T;
	while (T--) {
		m.clear();
		for (int i = 1; i <= 200000; i++) {
			parent[i] = i;
			cnt[i] = 1;
		}

		cin >> F;
		int index = 1;
		for (int i = 0; i < F; i++) {
			string a, b;
			cin >> a >> b;
			if (m[a] == 0) 
				m[a] = index++;
			if (m[b] == 0) 
				m[b] = index++;

			cout << Union(m[a], m[b]) << "\n";
		}
	}
}
μ €μž‘μžν‘œμ‹œ (μƒˆμ°½μ—΄λ¦Ό)
'πŸ“ Computer Science/✏ Algorithm' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [C++] λΉ„νŠΈλ§ˆμŠ€ν¬(BitMask)
  • [C++] 트라이(Trie)
  • [C++] 투 포인터(Two Pointer)
  • [C++] next_permutation, prev_permutation
Blxxming
Blxxming
CS 지식과 κ³΅λΆ€ν•˜λ‹€ 배운 것, κ²½ν—˜ν•œ 것 등을 κΈ°λ‘ν•˜λŠ” λΈ”λ‘œκ·Έμž…λ‹ˆλ‹€.
  • Blxxming
    πŸ’‘λ²ˆλœ©πŸ’‘
    Blxxming
  • 전체
    였늘
    μ–΄μ œ
  • 곡지사항

    • Tech Interview
    • πŸ“š Tech (246)
      • πŸ“ Computer Science (96)
        • ✏ OS (12)
        • ✏ Network & Web (10)
        • ✏ Database (11)
        • ✏ Data Structure (6)
        • ✏ Algorithm (40)
        • ✏ Design Pattern (9)
        • ✏ Cloud Computing (3)
        • ✏ (5)
      • πŸ“ Language (73)
        • ✏ Language (6)
        • ✏ C & C++ (11)
        • ✏ C# (19)
        • ✏ JAVA (37)
      • πŸ“ Game (43)
        • ✏ Computer Graphics (2)
        • ✏ Unity (14)
        • ✏ Unreal (26)
        • ✏ (1)
      • πŸ“ Book (34)
        • ✏ Effective (3)
        • ✏ Game Server (16)
        • ✏ Clean Code (14)
        • ✏ (1)
  • hELLOΒ· Designed Byμ •μƒμš°.v4.10.0
Blxxming
[C++] μœ λ‹ˆμ˜¨ νŒŒμΈλ“œ(Union-Find)
μƒλ‹¨μœΌλ‘œ

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”