UVA - 1160 - X-plosives

문제링크
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3601


문제해설
한 라인에 2개의 숫자가 스페이스 하나로 구분되어 들어온다.
이 숫자들이 들어올때 이전까지 들어온 모든 숫자쌍들을 확인하여서 N개의 숫자가 N쌍이 되는 경우가 생기면 폭발이 일어나게 된다.


예
1 2
2 1

1과 2 2개의 숫자로 2개의 쌍이 존재하므로 폭발

1 4
2 4
1 2

1 2 4. 3개의 숫자로 3개의 쌍이 존재하므로 폭발

1 4
1 5
4 1

1 4 5. 3개의 숫자로 3개의 쌍이 존재하므로 폭발
또는
1 4. 2개의 숫자로 2개의 쌍이 존재하므로 폭발.

이런식으로 폭발이 일어나게 되는 쌍이 들어오게 되면 갯수를 카운트하고, 해당 쌍은 받지 않는다. (다음 입력값을 받을때 계산에 포함시키지 않음)

처음에는 단순히 그래프의 cycle을 이용하여 풀어보려고 했지만. 뭔가 예외처리가 많아지고 깔끔하게 계산이 안되서 계속 고민하다가 집합을 이용하면 될 것 같아서 집합을 이용해서 풀었다.


풀이
만약 1 2 두개의 값을 가진 집합이 존재한다고 생각해보자.
이때 다음 입력으로 1과 X(2가 아닌)가 들어왔다고 생각해보자.
그럼 3개의 숫자로 2개의 쌍이 존재한다.
그런다음 다시 숫자가 들어오는데 2와 Y(1과 X가 아닌)가 들어왔다고 생각해보자.
그럼 4개의 숫자로 3개의 쌍이 존재하게 된다.

간단하게 말해서 들어온 2개의 숫자가 모두 한 집합에 존재하게 되면 이미 N개의 숫자로 N-1 개의 쌍이 이루어진 집합에서 N개의 숫자, N개의 쌍이 되는 집합이 되므로 무조건 폭발하게 된다.
만약 서로 다른 집합의 숫자가 들어왔다고 가정해보면 (X, X-1) 집합과 (Y, Y-1) 집합이 같은 각 집합들에 존재하는 숫자 1개씩으로 묶어주므로 (Z(X|Y), Z-1(X-1+Y-1+1)) 의 집합으로 변한다. 역시 이후 Z에 존재하는 두개의 쌍 숫자가 들어오면 폭발하게 된다.


슈도코드
집합은 단순 배열에다가 특정 idx의 값을 parent node의 idx로 주는 식으로 하여 집합의 root는 arr[idx] == idx 형식으로 만들어주면 된다. 특정 idx의 root를 구해줄때 idx의 값을 계속 거슬러 올라가는 식으로 계산해주면 된다.

  scanf("%d%d", &input1, &input2);

  if (setArr[input1] == -1)
    setArr[input1] = input1;
  if (setArr[input2] == -1)
    setArr[input2] = input2;

  head1 = GetRoot(input1);
  head2 = GetRoot(input2);

  if (head1 == head2)
    count++;
  else
    SetRoot(input2, head1);