UVALive - 3644 X - Plosives (및 검색 집합)
976 단어 데이터 구조데이터 구조 - 검색 집합
제목: K 개의 간단 한 화합물 을 제시 합 니 다. 마침 K 가지 요 소 를 포함 하고 있 습 니 다. 그러면 그들 을 차 에 실 을 때 이미 받 은 화합물 을 다시 가 져 올 때 는 차 에 싣 는 것 을 거절 하고 안전 하 게 한 다음 에 차 에 실 을 화합물 목록 을 드 립 니 다. 차 에 싣 는 것 을 거절 하 는 횟수 가 필요 하 냐 고 물 었 습 니 다.
문제 풀이 사고: 그리고 집 을 찾 습 니 다.이미 설 치 된 화합물 을 기록 하면 다음 화합물 이 이미 집합 중이 라면 선적 을 거부 해 야 한 다 는 뜻 이다.
코드:
#include
#include
const int maxn = 1e5 + 5;
int p[maxn];
void init () {
for (int i = 0; i < maxn; i++)
p[i] = i;
}
int getParent(int a) {
return a == p[a] ? a: p[a] = getParent (p[a]);
}
int main () {
int a, b;
int ans;
while (scanf ("%d", &a) == 1) {
ans = 0;
init();
do {
scanf ("%d", &b);
int q1 = getParent(a);
int q2 = getParent(b);
if (q1 == q2)
ans++;
else
p[q1] = q2;
} while (scanf ("%d", &a) && a != -1);
printf ("%d
", ans);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
