모음 집 - 템 플 릿
class DisjointSet
{
private:
int *father, *rank;
public:
DisjointSet(int size)
{
father = new int[size];
rank = new int[size];
for (int i = 0; i < size; ++i)
{
father[i] = i;
rank[i] = 0;
}
}
~DisjointSet()
{
delete[] father;
delete[] rank;
}
int find_set(int node)
{
if (father[node] != node)
{
father[node] = find_set(father[node]);
}
return father[node];
}
bool merge(int node1, int node2)
{
int ancestor1 = find_set(node1);
int ancestor2 = find_set(node2);
if (ancestor1 != ancestor2)
{
if (rank[ancestor1] > rank[ancestor2])
{
swap(ancestor1, ancestor2);
}
father[ancestor1] = ancestor2;
rank[ancestor2] = max(rank[ancestor2], rank[ancestor1] + 1);
return true;
}
return false;
}
int find_father(int node)
{
return father[node];
}
};
2017 - 3 - 23 NOIP Day 232
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[UOJ#149] [NOIP2015] 하위 문자열(dp)전송문 f(i, j, k)를 설정하면 a의 전 j 문자에서 i단을 선택하여 연결하면 b의 전 k개와 일치하는 방안 수를 나타낸다.g(i, j)는 a의 i번째 문자와 b의 j번째 문자가 뒤에서 앞으로 최대 몇 개까지 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.