백준 1717번: 집합의 표현(골드 IV)
게시글 주소: https://orbi.kr/00060992012
귀찮아서 문제는 생략
대충 유니온 파인드(Union-Find)를 구현하라는 문제입니다.
근데 이제 경로 압축(weighted-union heuristic)을 하지 않으면 시간 초과로 터집니다 낄낄
제가 아직 전공생이 아니라서 영문명이 맞나 모르겠네요
아무튼
#include <stdio.h>
int parent[1000001];
int main()
{
int i,n,m;
int Do,a,b;
scanf("%d%d",&n,&m);
for(i=0; i<n+1; i++)
parent[i] = i;
for(i=0; i<m; i++)
{
scanf("%d %d%d",&Do,&a,&b);
if(Do)
printf("%s\n", find(a)-find(b)?"NO":"YES");
else
merg(a,b);
}
}
int find(int x)
{
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void merg(int x, int y)
{
x = find(x);
y = find(y);
if (x>y)
parent[y] = x;
else
parent[x] = y;
}
+숏코딩 랭킹을 보면, find함수와 merg함수를 이렇게 축약할 수도 있습니다
f(a){return v[a]-a?v[a]=f(v[a]):a;}
u(a,b){v[f(a)]=f(b);}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
강대 2관,별관이 그렇게 별로라던데 진짜인가요?? 본관 안되면 차라리 안가는게...
컴공가면 이런거 하나요?
네
요건 생기초라 보심 될듯
정보올림피아드에서 본것만같은 내용들이네요
이게 뭐하는지 간략하게 설명하자면
어떤 데이터들의 집합이 있을때, 얘가 거기 안에 들어있냐 묻는겁니다
ex) {사과,배,감} {수박,딸기}이라는 데이터가 있을때, 사과가 1번 집합에 있냐를 묻는
ㄱㅁ
이왜기12번째 줄에 i<n+1을 i<n으로 써서 2시간동안 찾았어요
컴공에선 흔한일이죠코딩의 꽃은 디버깅입니다
그쵸 이게 PS의 맛이죠
드디어 골드 문제 리뷰를 오르비에서도 보다니 ㄷㄷ
플레티넘 문제도 리뷰하고싶어요