그래프에서 서로 연결된 세 정점의 차수 합의 최솟값 찾기

17089번: 세 친구 (acmicpc.net)

 

서로 친구인 a,b,c에 대하여 a의 친구 수 + b의 친구 수 + c의 친구 수가 최소가 되도록 만들고 싶다.

 

a의 친구 수에는 b,c는 제외해야한다.

 

마찬가지로 b,c의 친구 수에는 a,c, a,b는 제외해야한다.

 

a의 친구 수 + b의 친구 수 + c의 친구 수 - 6의 최솟값을 찾아야한다는 소리

 

친구 관계를 그래프로 만드는데 각 정점에 연결된 정점을 set()으로 만들어서 O(1)로 서로 친구인 정점을 찾도록 만들자

 

from sys import stdin

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

graph = [set() for _ in range(n+1)]

for _ in range(m):

    a,b = map(int,stdin.readline().split())
    graph[a].add(b)
    graph[b].add(a)

 

 

정점 a를 1번부터 n번까지 순회해서, 서로 친구인 세 정점 a,b,c를 찾아야하므로

 

a에 연결된 정점 수가 2이상인 경우만 해당이 된다

 

for a in range(1,n+1):
    
    if len(graph[a]) >= 2:

 

 

if len(graph[a]) >= 2를 안하면 시간이 100배 더 오래걸리더라

 

이거 하니까 시간이 100배 더 빨라짐..

 

아무튼

 

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

 

이 조건을 만족하는 정점 a에 대하여, a에 연결된 정점 graph[a]를 다시 순회해서 그들을 b로 하면

 

a,b는 친구가 된다

 

for a in range(1,n+1):
    
    if len(graph[a]) >= 2:
        
        for b in graph[a]:

 

 

마찬가지로 b의 정점과 연결된 정점들 graph[b]에서 순회하면 그 c는 일단 b랑은 친구고

 

a와도 친구여야 하므로, c in graph[a]가 만족해야한다

 

이걸 O(1)에 하기 위해 연결된 정점들을 set()으로 관리함

 

for a in range(1,n+1):
    
    if len(graph[a]) >= 2:
        
        for b in graph[a]:
                
            for c in graph[b]:

                if c in graph[a]:

 

 

 

이렇게 하면 서로가 친구인 3명 a,b,c를 찾았으니 len(graph[a]) + len(graph[b])  + len(graph[c]) - 6의 최솟값을 찾으면 된다

 

최솟값이 갱신이 안되면 그러한 세 친구 a,b,c를 찾을 수 없다는 뜻

 

조금 더 섬세한 테크닉으로

 

a를 1번부터 n번까지 순회하고 graph[a]에서 b를 순회하고 graph[b]에서 c를 순회해서

 

(a,b,c)를 찾는데

 

예를 들어 (1,3,5)를 찾았다고 해보자

 

a = 3이 되면 1번과 3번은 서로 친구이므로 (3,1,5)가 나오는데 

 

3번 친구의 합 + 1번 친구의 합 + 5번 친구의 합은 당연히 1번 친구의 합 + 3번 친구의 합 + 5번 친구의 합과 같다

 

그러니까 a < b < c를 만족하는 a,b,c를 찾으면 중복 계산을 더 줄일 수 있다

 

from sys import stdin

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

graph = [set() for _ in range(n+1)]

for _ in range(m):

    a,b = map(int,stdin.readline().split())
    graph[a].add(b)
    graph[b].add(a)

INF = 10**18

answer = INF

for a in range(1,n+1):
    
    if len(graph[a]) >= 2:
        
        for b in graph[a]:
            
            if b > a:
                
                for c in graph[b]:

                    if c > b and c in graph[a]:

                        v = len(graph[a]) + len(graph[b]) + len(graph[c]) - 6

                        if answer > v:

                            answer = v

if answer == INF:
    
    print(-1)

else:

    print(answer)