그래프에서 역방향 간선을 놓아 노드들의 크기 순서를 찾는 테크닉(도달 가능성)

1. 문제

 

2458번: 키 순서

 

 

1번부터 n번까지 번호가 붙여진 학생들의 키 순서가 주어진다.

 

예를 들어 1번 < 5번, 3번 < 4번, 5번 < 4번,....

 

이 결과로 모든 학생중 키가 가장 작은 학생부터 자신이 몇번째 학생인지 알 수 있는 학생도 있고, 

 

그렇지 못한 학생들도 있다.

 

이러한 결과가 주어질때 자신의 키가 몇번째 학생인지 정확히 알 수 있는 학생 수를 구한다

 

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

 

상식적으로? 먼저 생각해보면

 

i번이 몇번째 순서인지 알고 싶다면 i번보다 키가 큰 학생의 수, 키가 작은 학생의 수를 찾으면 알 수 있다

 

1번 < 5번

 

5번 < 4번

 

5번 < 2번

 

3번 < 4번

 

4번 < 6번

 

4번 < 2번

 

4번보다 키가 작은 학생은 1번, 3번, 5번

 

4번보다 키가 큰 학생은 2번, 6번

 

따라서 4번 학생은 위로 2명 있고 아래로 3명 있으므로 3등임을 정확히 알 수 있다

 

하지만 1번 학생보다 키가 큰 학생은 5번, 4번, 2번, 6번

 

그치만 1번과 3번 학생 사이를 비교할 수 없기 때문에 1번이 정확히 1등인지 2등인지는 알 수 없다

 

그래서 n명 있을때 자기보다 키가 큰 학생의 수 + 자기보다 키가 작은 학생의 수 = n-1이면 그 사람의 등수는 정확히 알 수 있다

 

그러면 키 관계가 주어질때 그래프로 만들고 i번에서 도달 가능한 정점을 모두 찾는다

 

a,b가 주어지면 a 에서 b로 갈 수 있다는 뜻이고 키 관계는 a < b라는 뜻

 

처음에 생각한건 n <= 500이라 무난하게 플로이드 워셜

 

dp[a][b] = 1로 두고, 모든 정점을 돌아 dp[a][b]값을 갱신하고, 

 

모든 i = 1,2,..,n에 대하여 dp[i][j] >= 1이면 i에서 j로 갈 수 있다는 뜻이고, i보다 키가 큰 학생이 j라는 뜻

 

dp[j][i] >= 1이면 j에서 i로 갈수 있다는 뜻인데 i보다 키가 작은 학생이 j라는 뜻이 될 것

 

두 학생의 수가 n-1이면 i번은 키가 몇번째인지 알 수 있게 된다

 

from sys import stdin

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

INF = 10**9

dp = [[INF]*(n+1) for _ in range(n+1)]

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

    #a < b
    dp[a][b] = 1

for i in range(1,n+1):
    
    dp[i][i] = 0

for k in range(1,n+1):
    
    for a in range(1,n+1):
        
        for b in range(1,n+1):
            
            if dp[a][k] + dp[k][b] < dp[a][b]:
                
                dp[a][b] = dp[a][k] + dp[k][b]

count = 0

for i in range(1,n+1):
    
    big = 0
    small = 0
    
    for j in range(1,n+1):
        
        if dp[i][j] != INF and dp[i][j] >= 1:
            
            big += 1
        
        if dp[j][i] != INF and dp[j][i] >= 1:
            
            small += 1
    
    if big + small == n-1:
        
        count += 1

print(count)

 

 

 

이 방법은 n이 커지면 힘들다

 

그래서 a에서 b로 갈 수 있는 간선을 가진 그래프 g 하나랑,

 

b에서 a로 갈 수 있는 역방향 간선을 가진 그래프 r_g 하나를 하나 더 만들고

 

두 그래프 각각에서 i번에서 도달 가능한 정점의 수를 찾는다

 

g에서 도달 가능한 정점들은 a보다 키가 큰 학생이 될거고 r_g에서 도달 가능한 정점들은 a보다 키가 작은 학생들

 

도달 가능한 정점 수의 합이 n-1이면 i번은 등수를 정확히 알 수 있다

 

모든 i = 1,2,..,n에 대해 각각 dfs 2번씩만 하면 각 정점이 몇등인지 정확히 알 수 있는 정점들을 찾을 수 있다

 

from sys import stdin

def dfs(u,g,visited):
    
    for v in g[u]:
        
        if visited[v] == 0:
            
            visited[v] = 1
            dfs(v,g,visited)

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

g = [[] for _ in range(n+1)]
r_g = [[] for _ in range(n+1)]

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

    #a < b
    g[a].append(b)
    r_g[b].append(a) 

count = 0

for i in range(1,n+1):
    
    visited = [0]*(n+1)
    visited[i] = 1

    dfs(i,g,visited)

    x = sum(visited)-1

    visited = [0]*(n+1)
    visited[i] = 1

    dfs(i,r_g,visited)

    y = sum(visited)-1

    if x+y == n-1:
        
        count += 1

print(count)

 

 

 

visited는 i부터 시작해서 방문한 정점들을 체크한 배열이니까 

 

visited[v] = 1

dfs(v)

 

하고 나서 visited[v] = 0으로 복구해버리면 안되겠지

 

 

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

 

 

2. 비슷한 문제

 

17616번: 등수 찾기

 

 

순서 관계가 주어지는 똑같은 문제인데 이번에는 x번 학생에 대해 이 학생이 몇등부터 몇등까지 가능한지를 찾는 문제

 

이번엔 n <= 10^5라서 dfs로 접근해야한다

 

그냥 간선을 가진 그래프를 놓고, 역방향 간선을 가진 그래프를 추가로 둔다

 

그러면 각각에 대해서 dfs를 수행하면 도달 가능한 정점을 찾을 수 있다

 

이때 x번 학생에 대해 더 큰 노드를 가진 학생 수가 a명

 

x번 학생에 대해 더 작은 노드를 가진 학생 수가 b명

 

그러면 x번의 순위 범위는?

 

예를 들어 총 7명 있다고 할때

 

1,2,3,4,5,6,7

 

x번의 위로 1명 도달 가능하고 아래로 3명 도달 가능하다고 한다면?

 

2등,3등,4등 중 하나 가능하다

 

위로 2명 도달 가능하고 아래로 2명 도달 가능하다고 한다면?

 

3등,4등,5등 가능하다

 

위로 a명 도달 가능하고, 아래로 b명 도달 가능하다고 한다면?

 

1 + a등부터 n - b등까지 가능하게 된다

 

from sys import stdin

def dfs(u,edge):

    for v in edge[u]:
        
        if visited[v] == 0:
            
            visited[v] = 1
            dfs(v,edge)
        
        
n,m,x = map(int,stdin.readline().split())

edge = [[] for _ in range(n+1)]
r_edge = [[] for _ in range(n+1)]

for _ in range(m):
    
    a,b = map(int,stdin.readline().split())
    edge[a].append(b)
    r_edge[b].append(a)

visited = [0]*(n+1)
visited[x] = 1
dfs(x,edge)

win = sum(visited) - 1

visited = [0]*(n+1)
visited[x] = 1
dfs(x,r_edge)

lose = sum(visited) - 1

print(1 + lose, n - win)