μ λμ¨ νμΈλ(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";
}
}
}