인접행렬에서 universal sink의 존재여부 O(n)에 판단하기

참고 사이트 : www.geeksforgeeks.org/determine-whether-universal-sink-exists-directed-graph/

introduction to algorithm 책의 22장 그래프 22.1_6번 문제이다.

 

방향 그래프 G에 대해 인접 행렬이 주어졌을 때,

universal sink(진입차수가 [v]-1이고, 진출차수가 0인 노드)의 존재여부를 O(n)에 판단하는지 여부를 보이는 문제인데

인접행렬의 시간복잡도가 O(n^2)인 반면 , O(n)에 해결해야 하기 때문에 모든 edge의 정보를 다 봐서는 해결할 수 없다.

 

인접행렬의 한 성분 a[i][j]의 값이 0이면, j의 indegree가 [v}-1

보다 작아지므로, j번 노드가 sink가 아님을 알 수 있다.

반대로 a[i][j]의 값이 1이면, i의 outegree가 0이 아니게 되므로, i번 노드가 sink가 아님을 알 수 있다.

즉, 한 행렬의 한 성분을 보면, 무조건 둘 중 하나에 해당하는 노드가 sink가 아니라는 정보를 얻을 수 있다.

 

 

확인해야될 행의 인덱스를 i, 열의 인덱스를 j라고 하자.

 

처음에는 전부 확인해야 하므로, 전부 1에서 시작한다.

한 번 루프를 거칠때마다, i,j 둘중 하나가 증가하므로,

만약 행의 인덱스가 i이면, [1~i-1]까지의 노드들은 전부 sink가 아닌 것임이 자명하다.

 

위 루프를 끝냇을 때, i의 인덱스가 n이하이면,

해당하는 i가 sink인지를 행렬에서 [i]를포함하는 성분을 O(n)으로 한번 다시 봐줌으로써 확인 가능하다.

 

한 성분 a[i][j]로 부터 얻을 수 있는 정보를 찾고, 이를 이용하여 효율적으로 봄으로써(한번 본것은 다시보지않기)

시간복잡도를 줄일 수 있다는 것을 다시한번 느끼고 가는 문제였다.

<코드>

/*introduction to algorithm (22_1-6.cc)
    노드가 n개인 그래프가 인접행렬 형태로 주어졌을때
    O(n)시간안에 universal sink 존재여부 알아보기
*/
#include<iostream>
int n, m;
using namespace std;
const int N = 1001;
bool a[N][N];
 
// sink node가 존재하면 그 노드의 번호를 return
// 없을시 -1 return
int sinkExist() {
    int i = 1, j = 1;
    // i번노드가 sink인지 아닌지 확인해야한다.
    while (i <= n && j <= n) {
        if (a[i][j])i++;
        else j++;
    }
    // 
    if (i > n)return -1;
 
    // i번 노드가 sink인지 다시한번 확인해야 한다.
    for (int j = 1; j <= n; j++) {
        if (i == j)continue;
        if (a[i][j])return -1;
        if (!a[j][i])return -1;
    }
    return i;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; // edge u - > v
        cin >> u >> v;
        a[u][v] = 1;
    }
    cout << sinkExist();
}