1717번 - 집합의 표현
#include
long long int p[1000000]; <----------가 1000001이어야 하는데 1000000을 넣어도 "맞았습니다"가 뜹니다. 테스트 케이스 수정 부탁드립니다.
int faind(int x)
{
if(p[x]==x) return x;
else return p[x] = faind(p[x]);
}
void onion(int x, int y)
p[faind(x)] = faind(y);
int main()
int n, m, k, a, b;
scanf("%d%d", &n, &m);
for(int i=0;i<=1000000;i++) p[i] = i;
for(int i=1;i<=m;i++)
scanf("%d%d%d", &k, &a, &b);
if(k==1)
if(faind(a)==faind(b)) printf("yes\n");
else printf("no\n");
}else onion(a, b);
assert문으로 확인 결과 n = 1000000인 입력이 존재합니다.
인덱스를 넘어가는 Index Out of Bound는 Undefined Behavior이므로 "맞았습니다"가 뜰 수도 있습니다.
댓글을 작성하려면 로그인해야 합니다.
ohhyundo12 3년 전
#include
long long int p[1000000]; <----------가 1000001이어야 하는데 1000000을 넣어도 "맞았습니다"가 뜹니다. 테스트 케이스 수정 부탁드립니다.
int faind(int x)
{
if(p[x]==x) return x;
else return p[x] = faind(p[x]);
}
void onion(int x, int y)
{
p[faind(x)] = faind(y);
}
int main()
{
int n, m, k, a, b;
scanf("%d%d", &n, &m);
for(int i=0;i<=1000000;i++) p[i] = i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d", &k, &a, &b);
if(k==1)
{
if(faind(a)==faind(b)) printf("yes\n");
else printf("no\n");
}else onion(a, b);
}
}