글 읽기 - 1717번 집합의 표현 문제에서 거부된 시스템 콜 에러가 납니다;

wwiiiii 9년 전 0

사용한게 배열, 벡터밖에 없는데... 왜 이런 오류가 나는걸까요 ㅠ?

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m;
int arr[1000010];//-1이면 루트노드, 아니면 부모노드를 가리킴

int represent(int k)//return the root value
{
	vector<int> container;
	while(arr[k]!=-1)
	{
		container.push_back(k);
		k = arr[k];
	}
	for(vector<int>::iterator it = container.begin();it!=container.end();++it) arr[*it] = k;
	return k;
}

int main()
{
	int query, a, b;
	scanf("%d %d",&n,&m);
	fill(&arr[0],&arr[1000010],-1);
	while(m--)
	{
		scanf("%d %d %d",&query,&a,&b);
		if(query==1)
		{
			if(represent(a)==represent(b)) puts("YES");
			else puts("NO");
		}
		else//a, b합집합
		{
			if(a==b) continue;
			else if(a>b) arr[represent(a)] = b;
			else arr[represent(b)] = a;
		}
	}

	return 0;
}

Nada 9년 전 0

5 5

0 2 3

0 1 4

0 2 4

1 3 2

무한 루프가 돌아서 vector의 heap 메모리를 초과했습니다.

if문이 잘못되었네요.

wwiiiii 9년 전 0

감사합니다! 빼먹은 부분 있었네요

합집합 연산 똑같은 집합끼리 합집합 시키는 쿼리를 무시하는 부분이 잘못됐었네요ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m;
int arr[1000010];//-1이면 루트노드, 아니면 부모노드를 가리킴
 
int represent(int k)//return the root value
{
    vector<int> container;
    while(arr[k]!=-1)
    {
        container.push_back(k);
        k = arr[k];
    }
    for(vector<int>::iterator it = container.begin();it!=container.end();++it) arr[*it] = k;
    return k;
}
 
int main()
{
    int query, a, b;
    scanf("%d %d",&n,&m);
    fill(&arr[0],&arr[1000010],-1);
    while(m--)
    {
        scanf("%d %d %d",&query,&a,&b);
        if(query==1)
        {
            if(represent(a)==represent(b)) puts("YES");
            else puts("NO");
        }
        else//a, b합집합
        {
            if(represent(a)==represent(b)) continue;
            else if(a>b) arr[represent(a)] = b;
            else arr[represent(b)] = a;
        }
    }
 
    return 0;
}

Nada 9년 전 0

그리고 if(a>b) 이 부분에서 if(rep(a) > rep(b)) 로 해주셔야 의도하신

부모가 항상 자기자신보다 작은 값을 가진다 라는 조건이 만족할 거에요.

wwiiiii 9년 전 0

그게 루트면 -1이 배열 인덱스로 들어가서요 ㅠㅠ 저도 그렇게 하고싶은데 꼬일거같아서

Nada 9년 전 2

루트일 때 -1 대신 자기자신으로 해두고

while문 체크할 때 -1대신 k != arr[k] 이런식으로 하면

구현 가능 할 거에요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1717번 집합의 표현 문제에서 거부된 시스템 콜 에러가 납니다;

wwiiiii 9년 전 0

Nada 9년 전 0

wwiiiii 9년 전 0

Nada 9년 전 0

wwiiiii 9년 전 0

Nada 9년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말