[백준/27726] 굉장한 모비스터디 (Python)

Problem : https://www.acmicpc.net/problem/27726

27726번: 굉장한 모비스터디

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:35:06

 

---

 

문제 설명

 

현대 모비스는 직원들이 소프트웨어 직무 교육을 이수할 수 있는 소프트웨어 아카데미를 2018년부터 운영하고 있다.

이 소프트웨어 아카데미에서는 총 세 번의 수업이 진행된다. 더 효과적인 학습을 위해 아카데미를 다니고 있는 N명의 직원들은 매 수업이 끝난 후 스터디를 진행하고자 한다.

스터디를 같이하는 구성원은 매 수업이 끝난 후 두 직원 간의 합의로 이루어진다. 만약 a번 직원과 b번 직원이 합의하였다면, 두 직원은 같이 스터디를 하게 된다. 이때 스터디를 같이 하는 직원들의 2명 이상의 모임을 모비스터디라고 한다. a번 직원과 b번 직원이 합의했고 b번 직원과 c번 직원 또한 합의했다면, a, b, c번 직원은 모두 같은 모비스터디이다.

굉장한 모비스터디를 다음과 같이 정의하자.

어떤 직원들이 세 번의 스터디에서 모두 같은 모비스터디에 속하고,
그 외의 직원들 중 어떤 직원도 이 모비스터디에 속한 직원들과 세 번의 스터디 모두를 같이 하지 않았다면
이 모비스터디는 굉장한 모비스터디다.

굉장한 모비스터디를 찾자.

 

입력 및 출력

 

입력

 

첫째 줄에는 아카데미를 다니고 있는 직원의 수 N(1 <= N <= 100000)이 주어진다.

둘째 줄에는 세 번의 스터디에서 이루어진 합의의 수 M1, M2, M3가 공백으로 구분되어 주어진다 (1 <= M1, M2, M3 <= 100000)
이후 M_1개의 줄에는 첫 번째 스터디에서 합의한 서로 다른 두 직원의 번호 a와 b가 공백을 두고 주어진다.

이후 M_2개의 줄에는 첫 번째 스터디에서 합의한 서로 다른 두 직원의 번호 a와 b가 공백을 두고 주어진다.

이후 M_3개의 줄에는 첫 번째 스터디에서 합의한 서로 다른 두 직원의 번호 a와 b가 공백을 두고 주어진다.

(a != b, 1 <= a, b <= N)

입력으로 주어지는 모든 값은 정수다.

 

출력

 

첫 번째 줄에는 굉장한 모비스터디의 수 K를 출력한다.

이후 K개의 줄에 걸쳐 굉장한 모비스터디에 포함된 직원들의 번호를 출력한다.

출력 형식은 다음과 같다.

서로 다른 굉장한 모비스터디의 경우 포함된 직원의 최소 번호가 더 작은 굉장한 모비스터디가 먼저 출력되어야한다.

예를 들어 두 굉장한 모비스터디가 각각 {3, 4}와 {1, 2, 5}라면 {1, 2, 5}가 먼저 출력되어야 한다.
같은 굉장한 모비스터디에 속한 직원들의 번호가 오름차순으로 정렬되어있어야 한다.
예를 들어 어떤 굉장한 모비스터디가 {3, 2, 6}이라면 {2, 3, 6}과 같이 출력되어야 한다.

 

입력 예시

 

5
3 4 3
1 2
2 3
4 5
1 2
2 3
3 4
4 5
2 3
1 4
4 5

 

출력 예시

 

2
2 3
4 5

 

 

---

 

풀이

 

M1, M2, M3에서 유니온 파인드를 진행한다. 그렇다면 같은 모비스터디에 속한 직원들은 같은 부모값을 가지게 될 것이다.

 

우리가 찾고 싶은 집합은 M1, M2, M3에서의 부모값이 동일한 직원들의 집합이다. 위에서 진행한 부모값을 기준으로 정렬을 수행한다면, 부모값이 전부 동일한 직원들은 인접하게 된다. 이 직원들을 순회하며 조건에 맞는 직원들의 집합을 찾으면 된다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
M_list = list(map(int, input().split()))
p = [[i]*3 for i in range(N+1)]

def find(a, i) :
  if a == p[a][i] :
    return a
  p[a][i] = find(p[a][i], i)
  return p[a][i]

def union(a, b, i) :
  pa, pb = find(a, i), find(b, i)
  if pa > pb :
    pa, pb = pb, pa
  p[pb][i] = pa

for i in range(3) :
  for _ in range(M_list[i]) :
    a, b = map(int, input().split())
    union(a, b, i)
  for j in range(1, N+1) :
    find(j, i)

p = sorted([[tuple(p[i]), i] for i in range(1, N+1)])
ans = []
tmp, prev = [p[0][1]], p[0][0]
for i in range(1, N) :
  if prev == p[i][0] :
    tmp.append(p[i][1])
  else :
    if len(tmp) > 1 :
      ans.append(sorted(tmp))
    tmp, prev = [p[i][1]], p[i][0]
if len(tmp) > 1 :
  ans.append(sorted(tmp))

print(len(ans))
for _ans in sorted(ans) :
  print(*_ans)