ABC 304 복기 - E good graph - union find 활용

1. 문제

 

E - Good Graph (atcoder.jp)

E - Good Graph

 

2. 풀이

 

그대로 구현하면 바로 시간초과 당하는데

 

조금만 생각하면 상당히 간단한 문제가 된다

 

N개의 정점을 가지고 M개의 간선을 가지는 그래프 G가 주어지는데 

 

모든 i = 1,2,3..,k에 대하여 G에 존재하는 두 정점 $x_{i}, y_{i}$가 서로 연결되어 있지 않다면, G가 good 그래프이다.

 

이 때, Q개의 query가 주어지는데,

 

그래프 내의 두 정점 $p_{i}, q_{i}$ 사이를 서로 무방향 간선으로 연결할때, 만든 새로운 그래프 $G_{i}$는 good 그래프인가?

 

---------------------------------------------------------------------------------------------------------

 

보자마자 union find 문제겠네 하고

 

일단 문제 접근을 상당히 잘하긴 했어

 

근데 그대로 구현할려고 하면 조금 까다롭다

 

u와 v가 서로 간선으로 연결되어 있다면, union으로 연결해서 그래프 G를 union-find 자료구조로 관리

 

k개의 x,y를 good이라는 리스트에 받은 다음에,

 

Q개의 p,q query를 받아서

 

p,q를 union 시키고,

 

good 리스트에서 x,y 순회한다음에 x,y의 parent를 찾아 parent가 서로 같다면 x,y는 연결되어 있으므로

 

하나라도 서로 연결된 경우라면 No

 

그렇지 않다면 Yes

 

그리고 나서 union시킨 p,q를 다시 ununion시켜줘야한다

 

이 부분이 상당히 문제다...

 

원본 parent를 항상 복사하면 O(N)이니까 당연히 시간초과일거고

 

from sys import stdin

def find_parent(x,parent):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent[x],parent)
    
    return parent[x]

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        parent[a] = b
    
    else:
        
        parent[b] = a

n,m =map(int,stdin.readline().split())

parent = [i for i in range(n+1)]

for _ in range(m):
    
    u,v = map(int,stdin.readline().split())

    union(u,v)

k = int(stdin.readline())

good = []

for _ in range(k):
    
    x,y = map(int,stdin.readline().split())

    good.append((x,y))

copy_parent = parent[:]

Q = int(stdin.readline())

for _ in range(Q):
    
    p,q = map(int,stdin.readline().split())

    union(p,q)

    no = False

    for i in range(k):
        
        a,b = good[i][0],good[i][1]

        a = find_parent(a,parent)
        b = find_parent(b,parent)

        if a == b:
            no = True
            break
    
    if no:
        
        print('No')
    
    else:
        
        print('Yes')
    
    parent = copy_parent[:]

 

나름 머리를 써가지고 union 함수에서 이전 기록을 저장해둔 다음에 return시켜가지고

 

query가 끝나면 복원시키는 방법을 써봤는데

 

from sys import stdin

def find_parent(x,parent):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent[x], parent)
    
    return parent[x]

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        x = parent[a]

        parent[a] = b

        return 0,x

    else:
        
        x = parent[b]

        parent[b] = a

        return 1,x

n,m =map(int,stdin.readline().split())

parent = [i for i in range(n+1)]

for _ in range(m):
    
    u,v = map(int,stdin.readline().split())

    union(u,v)

k = int(stdin.readline())

good = []

for _ in range(k):
    
    x,y = map(int,stdin.readline().split())

    good.append((x,y))

Q = int(stdin.readline())

for _ in range(Q):
    
    p,q = map(int,stdin.readline().split())

    p_parent = find_parent(p,parent)
    q_parent = find_parent(q,parent)

    ind,before = union(p,q)

    no = False

    for i in range(k):
        
        a,b = good[i][0],good[i][1]

        a = find_parent(a,parent)
        b = find_parent(b,parent)

        if a == b:
            no = True
            break
    
    if no:
        
        print('No')
    
    else:
        
        print('Yes')
    
    if ind == 0:
        
        parent[p_parent] = before
    
    else:
        
        parent[q_parent] = before

 

이렇게 하면 find_parent 함수 때문에 parent 배열이 다른 인덱스에서도 바뀌어가지고

 

원본 복원이 안되어가지고 오답이 나오더라고

 

그러면 경로압축을 하지 말고. 해볼까?

 

경로압축 + union 최적화나 둘중 하나만 하나 시간 차이가 거의 없었던걸로 기억하는데

 

from sys import stdin
 
def find_parent(x,parent):
    
    while x != parent[x]:
        
        x = parent[x]
    
    return x
 
def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)
 
    if parent[a] < parent[b]:
        
        x = parent[a]
 
        parent[a] = b
 
        return 0,x
 
    else:
        
        x = parent[b]
 
        parent[b] = a
 
        return 1,x
 
n,m =map(int,stdin.readline().split())
 
parent = [i for i in range(n+1)]
 
for _ in range(m):
    
    u,v = map(int,stdin.readline().split())
 
    union(u,v)
 
k = int(stdin.readline())
 
good = []
 
for _ in range(k):
    
    x,y = map(int,stdin.readline().split())
 
    good.append((x,y))
 
Q = int(stdin.readline())
 
for _ in range(Q):
    
    p,q = map(int,stdin.readline().split())
 
    p_parent = find_parent(p,parent)
    q_parent = find_parent(q,parent)
 
    ind,before = union(p,q)
 
    no = False
 
    for i in range(k):
        
        a,b = good[i][0],good[i][1]
 
        a = find_parent(a,parent)
        b = find_parent(b,parent)
 
        if a == b:
            no = True
            break
    
    if no:
        
        print('No')
    
    else:
        
        print('Yes')
    
    if ind == 0:
        
        parent[p_parent] = before
    
    else:
        
        parent[q_parent] = before

 

근데 이래도 시간 차이가 없더라...

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

union을 안해봐도 쿼리를 해결할 수 있는 놀라운 사고 방식이 있다

 

그래프 G를 union find 자료구조로 관리하고,

 

k개의 good 리스트의 원소 x,y에 대하여 x,y의 parent를 미리 찾아두고, good 리스트에 저장해둔다

 

이 때 중요한 점은 애초에 제약사항에서 "x,y의 connection은 되어 있지 않다"라고 명시되어 있다.

 

애초에 첫 그래프 G는 good 그래프인 상태로 주어진다는 뜻이다.

 

그리고 x,y가 달라도 소속된 그룹의 대표자를 나타내느 parent는 당연히 중복될 수 있다

 

그러니까 good 리스트를 set으로 관리해서 중복되는 것은 없앤다

 

그러한 리스트를 $$(parent(x_{1}), parent(y_{1})), ... (parent(x_{k}), parent(y_{k}))$$

 

그리고 쿼리를 받아서 p,q에 대해 p,q의 parent를 찾아본다.

 

$$(parent(p), parent(q))$$

 

여기서 한번 더 생각을 해본다.

 

--------------------------------------------------------------------------------

 

먼저 너가 잘못 생각한 점은,

 

p와 q를 union시키면 오직 p와 q가 어디 집합으로 속하게 되는거지, p와 q가 아닌 다른 정점은 그대로 있는거다..

 

p와 q가 집합으로 속하게 되면서 그 외의 정점이 어딘가로 바뀔리는 없다

 

-------------------------------------------------------------------------------

 

다음 위 사항을 명심하고..

 

p,q 사이 간선을 연결했다면, 두 대표자 (parent(p), parent(q))가 서로 같게 되겠지.

 

그리고 나서 good 리스트의 (parent(x), parent(y))가 서로 같은지 체크를 할건데...

 

p,q를 union 해보지 않고도 알 수 있는 방법은 무엇일까?

 

p,q를 union한다면 오직 (parent(p), parent(q))가 서로 같게 되므로...

 

만약에 p,q를 union 시켰을때, good 그래프가 안될려면

 

good 리스트의 (parent(x), parent(y))와 (parent(p), parent(q))와 같은 경우가 있어야한다.

 

 

p,q가 union되면 오직 (parent(p), parent(q))만 서로 같아지니까,

 

(parent(x),parent(y))가 (parent(p), parent(q))와 같다면...

 

p,q를 union 후에도 good 리스트 내의 어느 두 정점 x,y도 연결되었다는 뜻이니까, good이 안된다는 뜻이고

 

(parent(x),parent(y))가 (parent(p), parent(q))와 같은 경우가 없다면

 

p,q를 union 후에도 good 리스트 내의 어느 두 정점 x,y도 연결되지 않았다는 뜻이니까 good이 된다는 뜻이다

 

 

그러면 p,q를 union하지 않아도, p,q의 대표자를 구한다음에 good 리스트 내에 (parent(p), parent(q))가 존재하는지만 검사하면 된다.

 

from sys import stdin

def find_parent(x,parent):
    
    if x != parent[x]:

        parent[x] = find_parent(parent[x],parent)

    return parent[x]

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        parent[a] = b

    else:
        
        parent[b] = a

n,m =map(int,stdin.readline().split())

parent = [i for i in range(n+1)]

for _ in range(m):
    
    u,v = map(int,stdin.readline().split())

    union(u,v)

k = int(stdin.readline())

#x,y가 서로 다르더라도 대표자가 서로 같은 경우가 존재하므로
#set을 사용해 중복을 제거함
good = set()

for _ in range(k):
    
    x,y = map(int,stdin.readline().split())

    x = find_parent(x,parent)
    y = find_parent(y,parent)
    
    #무방향 그래프이므로, (x,y)를 연결하나 (y,x)를 연결하나 서로 같다
    if x > y:
      x,y = y,x
      
    good.add((x,y))

Q = int(input())

for _ in range(Q):
    
    p,q = map(int,stdin.readline().split())

    p = find_parent(p,parent)
    q = find_parent(q,parent)
    
    if p > q:
      p,q = q,p
    
    #(p,q)가 good에 존재한다는 뜻은
    #(p,q)를 연결하면 good의 어느 두 정점이 서로 연결된다는 뜻이다.
    #그러므로 good 그래프가 되지 않는다.
    if (p,q) in good:
        
        print('No')
    
    else:
        
        print('Yes')

 

여기서 중요한 점은 무방향 그래프이기 때문에 (x,y)를 연결하나 (y,x)를 연결하나 서로 같다.

 

그러므로 x > y이면 x,y를 뒤바꿔서 항상 두번째 원소가 더 큰 (x,y)로 일관되게 만들어주자.

 

접근은 잘 했는데

 

생각이 부족했다...