netstat: listen 하고 있는 포트들 확인

$ sudo netstat -tln
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
tcp        0      0 127.0.0.1:45249         0.0.0.0:*               LISTEN
tcp        0      0 0.0.0.0:9868            0.0.0.0:*               LISTEN
tcp        0      0 0.0.0.0:9993            0.0.0.0:*               LISTEN

lsof를 쓰게 되면 어떤 프로세스인지 확인할 수 있다.

$ sudo lsof -i -P -n | grep LISTEN
systemd-r    2642 systemd-resolve   14u  IPv4    25307      0t0  TCP 127.0.0.53:53 (LISTEN)
redis-ser    2796           redis    6u  IPv4    32072      0t0  TCP 127.0.0.1:6379 (LISTEN)
docker-pr 1047663            root    4u  IPv4 31617983      0t0  TCP *:9993 (LISTEN)
docker-pr 1047671            root    4u  IPv6 31620897      0t0  TCP *:9993 (LISTEN)

 

반응형

'Programming > Android' 카테고리의 다른 글

안드로이드 저장소(android storage), 파일 입출력  (2) 2019.03.06

여기여기여기, 여기 참조

특히 여기가 좋다.

 

완전이진트리 형태의 자료구조를 이용해서, element update가 존재하는 배열에 대해 특정 구간의 합, 곱, 최대값, 최소값 등을 효율적으로 구하는 자료구조

힙(heap)도 완전 이진트리를 이용하기 때문에 유사성이 있다고 볼 수 있다.

 

중간 중간에 element update가 존재하지 않는 경우, 세그먼트 트리까지는 필요없고 prefix sum등 간단한 테크닉을 쓰면 된다.

 

arr[12] = {3, 5, 6, 7, 2, 9, 4, 5, 2, 8, 1, 5} 이러한 배열이 있다고 하자.

 

완전이진트리 형태로 만들것이므로 $2^k >= 12$인 최소 k를 구해야한다. 

1
2
int k = (int)ceil(log2(n));
int tree_size = (1 << (k+1));  // base1 인덱스를 사용하기 때문에 +1을 해준다.
cs

 

 

반응형

여기여기여기, 여기 참조



수학적인 기초

먼저 절, 명제, 조건문 이 세가지가 헷갈리기 쉬운데, 이 알고리즘을 이해하려면 절대 헷갈리면 안된다.

절은 나중에 설명하고 명제부터 살펴보자.

명제란 대한민국의 수도는 서울이다, 사람은 날 수 있다. 처럼 true/false를 특정지을 수 있는 것을 말한다. 

나는 사람이다. 라는 명제를 P로 놓고, 나는 동물이다. 라는 명제를 Q로 놓은 다음 화살표로 연결하면

P->Q 이렇게 되고 조건문이된다.

조건문의 true/false는 생각보다 까다로운데 명제논리 링크를 참조해서 이해해보자.


P
Q
P → Q
T
T
T
T
F
F
F
T
T
F
F
T


위에서 다른건 다 상식선에서 이해가 되는데 P가 거짓이면 Q가 참이던 거짓이던 모순이 없는건 일상생활 명제에 대입하면 좀 받아들이기 힘들다.

(철희가 남자라면 철희는 남자가 아니다. 라는 조건문도 모순이 없는 참이 되어버리는 사태가 발생한다. 근데 생각해보면 남자라면 이라는게 거짓일때만 모순이 없는것이므로, 남자라는게 뻥이었으므로 뻥이 아닌 사실로는 남자일수도 있고 아닐수도 있는 상태가 되는걸로 이해는 가능하다. )

그럴때는 다음 문장을 참고해서 대략적으로 이해하고 넘어가자

P가 거짓일 때 참이되는 것이 아직 받아들이기 어렵다면 이렇게 생각해보자. 선생님이 학생에게 '체육대회에서 100m를 5초안에 뛸 수 있으면 72 km/h... 아이스크림을 주겠다'라고 말했다고 해보자. 이 말이 거짓말이 되는 경우는 "단 한가지" 뿐이다. 즉, (2) 학생이 100m를 5초 안에 들어왔는데 선생님이 아이스크림 안주는 경우만 거짓이다. (3) 학생이 5초안에 못뛰었을 때 선생님이 학생이 안쓰러워 아이스크림을 사준 경우 이는 선생님이 약속을 어겼다고 볼 수 없고 단순한 변심으로 보는게 타당할 것이다. 즉 위의 선생님의 약속(가언 명제) 자체는 여전히 이다. 그리고 마찬가지로 (4) 5초안에 못뛰었을 때 선생님이 아이스크림을 사주지 않는 경우 학생은 그런가보다 하고 넘어갈 수 있고 이 또한 선생님이 약속(가언 명제)을 어겼다고 할 수 없다. 즉, 으로 인정한다. 다시 정리하자면 학생이 100m를 5초 안에 뛰지 못한 경우에 대해서 선생님은 어떠한 약속도 하지않았으므로 선생님이 어떤 행동을 하든 약속이 거짓말이 될 수없다.[12]

2SAT이란

2-SAT(2-SATisfiability)문제는 충족 가능성 문제(satisfiability problem)의 한 종류입니다.

충족 가능성 문제란, 여러 개의 boolean변수들로 이루어진 식이 있을 때 각 변수에 값을 할당하여 식을 참으로 만드는 조합을 찾거나, 그러한 조합이 없음을 찾는 문제입니다.


f = (x2 ∨ ¬x1) ∧ (¬x1 ∨ ¬x2) ∧ (x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) ∧ (x1 ∨ x4)

이 식은 {x1 : false, x2 : false, x3 : true, x4 : true} 인 경우에 참이 됩니다.

가만 보면, 나이브한 솔루션은  x1~x4값에 대해서 0과1을 대입해보는 식으로 2^n의 모든 부분집합을 테스트해보면 된다는 사실을 알 수 있다. 


위에보면 괄호안에 두개의 변수가 들어있는데, 그래서 2-SAT이고, 괄호하나를 절(clause)이라고 부른다.

괄호안은 항상 OR 연산자, 괄호밖은 항상 AND연산자로 되어 있다. 

이렇게 절의 AND 연산으로만 표현된 식의 형태를 CNF(Conjunctive Normal Form)라고 합니다.


1SAT문제는 트리비얼하게 O(N)에 풀린다.

3SAT이상은 다항시간 솔루션이 없다.

신기하게도 2SAT문제도 선형시간에 풀린다!


여기까지만 들으면 이런걸 왜 보고 있나하는 생각이 드는데, 의외로 많은 문제들이 2-SAT으로 변환 가능하고, SCC로 풀수 있다고 한다.

여기 참조

1. 답이 존재하는지 여부 구하기

여기까지는 할만한 느낌

핵심아이디어

1. 논리식을 조건문으로 바꾼다 : (A∨B) = ¬A → B 와 ¬B → A  !!

A가 거짓이라면 B는 무조건 참이여야 하며, B가 거짓이라면 A는 무조건 참이여야 한다.

2. 모든 절의 명제들을 합하여 하나의 유향그래프를 생성할 수 있다.

3. 사이클 전체가 true이거나 전체가 false로 통일되어야한다. A와 ¬A이 같은 사이클에 있을 수 없다.

P
Q
P → Q
T
T
T
T
F
F
F
T
T
F
F
T

3번을 잘 이해해야 하는데, true -> false이면(사실 그럴때만) 조건문에 모순이 생긴다는 걸 기억하면 된다.

(p → q에서 p가 참일 때는 q는 무조건 참이여야하며 p가 거짓일 때는 q가 무엇이든지 상관없음)


따라서, A→¬A가 나오면 A는 반드시 false여야 한다.

마찬가지로 ¬A→A가 나오면 A는 반드시 true여야 함

근데 (하나의 사이클에서 ) A→¬A도 발견되고 ¬A→A도 발견된다? 그럼 false도 될수 없고, true도 될수 없어서 모순!

(여기서 한가지 중요한 관찰은 같은 SCC가 아니면서 A→¬A 또는 ¬A→A 이렇게 단방향은 있을 수 있다는 것이다. 일상언어 조건문으로 바꾸면 남자이면 남자가 아니다. 이런게 되어서 무지 이상하지만, 상단에 서술했듯이 수학적으로는 모순이 없다. 조건문 왼쪽에 거짓이기만 한다면.)


내 코드는 다음과 같다. 이 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
struct result { vi scc_map;  vvi scc_list; vvi scc_adj_list; };
result scc_dag_kosaraju(int max_v, vvi& adj_list, vvi& adj_rlist, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc, scc_list, scc_adj_list};
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int N, M; cin >> N >> M;
    vvi adj_list(2*+ 2), adj_list2(2*+ 2);
    for(int i=0;i<M;i++) {
        int a, b; cin >> a >> b;
        if (a < 0) a *= -2else a = a * 2 - 1;
        if (b < 0) b *= -2else b = b * 2 - 1;
        int na = (a % 2 == 0) ? a - 1 : a + 1;
        int nb = (b % 2 == 0) ? b - 1 : b + 1;
        //not a -> b
        adj_list[na].push_back(b);
        adj_list2[b].push_back(na); // 역방향
 
        //not b -> a
        adj_list[nb].push_back(a);
        adj_list2[a].push_back(nb); // 역방향
    }
    auto r = scc_dag_kosaraju(N*2+1, adj_list, adj_list2, true);
    int ok = 1;
    for(int i=1;i<=N;i++)
    {
        if (r.scc_map[i * 2== r.scc_map[i * 2 - 1]) ok = 0;
    }
    cout << ok << '\n';;
    return 0;
}
cs


2. 유효한 변수값들 구하기

난이도가 확 올라가는 느낌

여기여기 참조

추가로 필요한 아이디어

모든 정점에 대해서 위상정렬 순으로 처음만나면 거짓을 만들어주는식으로 채워주면 된다.

예를 들어 위상정렬순으로 not X3을 먼저 만났으면 not X3 = false 가 되어야 하므로 X3은 true로 확정해주는 식.

이런방법 말고도 굉장히 많은 방법이 있는것 같은데, 적당히 한가지로 외워두면 될듯하다.

아래는 내 코드고, 이 문제에 대한 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
struct result { vi scc_map;  vvi scc_list; };
result scc_dag_tarjan(vvi& adj_list, int base1)
{
    int max_v = (int)adj_list.size() - 1;  // base1==0일때 테스트 안됨!
    //타잔은 수행후 SCC들이 역순으로 위상정렬을 이루므로,
    //그 성질을 이용하면 좋다(2-SAT등)
 
    vvi ans;
    stack<int> S;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi scc_map(max_v + base1, -1), visit(max_v + base1), ord(max_v + base1), parent(max_v + base1); int g_ix = 0;
    // 코사라주나 단절선 구하는것과 다르게 finish 운영해줌
    // 일반적으로 finish배열이 dfs리턴할때 true해주는것과 다르게
    // SCC분리가 끝났음을 의미
    vi finish(max_v + base1);
    static int scc_ix = base1;
    function<int(int)> dfs = [&](int n)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        S.push(n);  // 스택에 먼저 푸시
        for (auto adj : adj_list[n])
        {
            if (visit[adj] == 0)  // tree edge 의 경우
            {
                int r = dfs(adj);
                // 단절점 로직의 경우 여기서 자식트리중 하나라도 자신위로 올라가지 못하면 단절점으로 판정하지만
                // SCC 타잔에서는 그러한 로직은 없고, 루프하단에 result == ord[n] 으로
                // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출하는 로직으로 바뀐다.
                // if (r > ord[n]) ans.insert({ min(n,adj), max(n,adj) });
                low = min(low, r);
            }
            // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
            else if (finish[adj] == 0)  // back edge 또는 cross edge의 일부
                low = min(low, ord[adj]);  // 접근가능한 백정점 순서로 업데이트
        }
        // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출
        if (low == ord[n])
        {
            vi scc;
            while (S.size())
            {
                int a = S.top(); S.pop();
                scc.push_back(a);
                scc_map[a] = scc_ix;
                finish[a] = 1;
                if (a == n) break;
            }
            sort(scc.begin(), scc.end());
            ans.push_back(scc);
            scc_ix++;
        }
 
        return low;
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    return { scc_map, ans };
}
 
#define DBL(a) (2*(a))
#define CONV(a) (a)<0?(a)*-2:(a)*2+1
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int N, M; cin >> N >> M;
    vvi adj_list(DBL(N+1));
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        a = CONV(a);
        b = CONV(b);
 
        //nice magic property!
        int na = a ^ 1;
        int nb = b ^ 1;
 
        //not a -> b
        adj_list[na].push_back(b);
 
        //not b -> a
        adj_list[nb].push_back(a);
    }
    auto r = scc_dag_tarjan(adj_list, true);
    for (int i = 1; i <= N; i++)
    {
        if (r.scc_map[CONV(i)] == r.scc_map[CONV(-i)]) { cout << 0 << '\n'return 0; }
    }
    // 여기까지 오면 변수조합이 있는건 보장된다. 모순만 없도록 배열해주면 됨
    cout << 1 << '\n';
    for (int i = 1; i <= N; i++) {
        // 아랫부분 아직 제대로 이해 못한 상태 ㅠ
        // 소스가 워낙 간결해서 일단 채택은 해 두었다.
        cout << (r.scc_map[CONV(i)] < r.scc_map[CONV(-i)]) << ' ';  
    }
    return 0;
}
 
cs



반응형

문제링크는 여기


풀이과정

출발점은 하나로 정해져 있고, 도착점은 여러개.

현금인출은 사이클 도는게 유리하므로 SCC단위로 생각하면 됨.

도착점도 SCC단위로 묶어서 생각하면 됨.

SCC단위로 묶고나서 보면, 간선 가중치는 없는 방향그래프 이므로, 위상정렬 개념 도입해서 longest 구하면 답

(여기서 위상정렬이 아닌 단순 BFS로는 안풀린다. 그래프 최장거리 참조)


헷갈렸던 점

아래 그래프가 SCC이후에 만들어진 DAG이라고 해보자. 

1번정점이 시작, 5번 정점이 끝이라고 해보자.


위의 그래프를 아래와 같은 코드로 위상정렬하면서 돌리게 되면

1
2
3
4
5
6
7
8
9
10
enqueue({ start_v, cost[start_v] });
while (q.size()) {
    auto n = q.front(); q.pop();
    max_dist[n.v] = max(max_dist[n.v], n.w);
    for (auto adj : adj_list[n.v]) {
        max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj]=1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}
cs


1번노드를 처리한다음에 2번 노드처리하기전에 while()이 끝나게 된다. (2번 노드의 in_edge가 3이라서 1빼도 아직 2라서 3과 4를 처리하기 전까진 못들어가는데 3,4를 처리하지 않는 코드이다.)

하지만 정답은 1 -> 2 -> 3을 모두 계산한 최대비용이 답이었던것.. 


따라서, 아래처럼 처음에 indegree가 0인 모든 정점을 queue에 넣어주고, cal[v] 맵을 사용해서 유효한 경우에만 max_dist가 갱신되도록 해주면 OK

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
if (start_v == -1for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
else max_dist[start_v] = cost[start_v];
vi cal(max_v + base1); cal[start_v] = 1;
while (q.size()) {
    auto n = q.front(); q.pop();
    for (auto adj : adj_list[n.v]) {
        if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}
cs



코드

scc_dag_kosaraju()를 라이브러리화 하고, 기존 longest()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*{{{*/
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
#define FileInput freopen("input.txt""rt", stdin)
#else
#define dbg(...)
#define FileInput
#endif
//#define int long long
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define CASE_T int ___T; cin>>___T;for(int cs=1;cs<=___T;cs++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define IN(n) int n;cin>>n
#define IN2(a,b) int a,b;cin>>a>>b
#define OUT(x) cout << (x) << endl
template <class T>
void OUTV(vector<T>& v) { REP(i, SZ(v)) cout << v[i] << (i + 1 == SZ(v) ? '\n' : ' '); }
typedef long long ll;
const int INF = (int)1e9;
/*}}}*/
 
struct result { vvi scc_list; vvi scc_adj_list; vi scc_cost; int scc_start_v; vi scc_end_v; };
result scc_dag_kosaraju(int max_v, int start_v, vi& end_v, vvi& adj_list, vvi& adj_rlist, vi& cost, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix); int scc_start_v = -1; vi scc_end_v(scc_ix), scc_cost(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        if (u == start_v) scc_start_v = scc[u];
        if (end_v[u]) scc_end_v[scc[u]] = 1;
        scc_cost[scc[u]] += cost[u];
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc_list, scc_adj_list, scc_cost, scc_start_v, scc_end_v };
}
struct node { int v, w; };
using vvn = vector<vector<node>>;
struct result2 { vi max_dist; int max_value; vi path; };
result2 longest(int max_v, int start_v, vvi& adj_list, vi& in_edge, vi& cost, vi& end_v, int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF);
    vi from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0return false;
        q.push(n);
        return true;
    };
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    if (start_v == -1for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
    else max_dist[start_v] = cost[start_v];
    vi cal(max_v + base1); cal[start_v] = 1;
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
            in_edge[adj]--;
            if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
        }
    }
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (end_v[i] && max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    FileInput;
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
    vi cost(V + 1);
    REP1(i, V)cin >> cost[i];
    IN2(S, P);
    vi end_v(V + 1);
    REP(i, P) { IN(p); end_v[p] = 1; }
    auto r = scc_dag_kosaraju(V, S, end_v, adj_list, adj_list2, cost, true);
    int N = SZ(r.scc_adj_list) - 1;
    vi in_edge(N + 1);
    REP1(u, N) for (auto v : r.scc_adj_list[u])in_edge[v]++;
    auto r2 = longest(N, r.scc_start_v, r.scc_adj_list, in_edge, r.scc_cost, r.scc_end_v, true);
    OUT(r2.max_value);
    return 0;
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

cph  (0) 2024.07.21
double과 관련된 핸들링  (0) 2021.12.26
백준 15481 그래프와 MST  (0) 2020.05.02
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09

여기, 여기 참조, 강한연결요소(SCC)의 타잔 알고리즘과 관련있다.

단절점

한덩이의 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상으로 나누어지면 단절점이라고 한다.

위 그래프에서 빨간정점들은 단절점이 된다. 따라서 개념은 무척쉽다.

단절점을 가장 Naive하게 찾아 볼 수 있는 방법은 모든 정점을 한번씩 선택하여(V) 제거한 후 그래프가 나뉘어지는지 파악해보는 방법이 있다(V + E). 따라서 시간 복잡도는 $O(V \times (V + E))$가 된다.

보통 나이브 하지 않은 구현은 O(V+E)의 복잡도를 가지는데, 여기가 가장 이해하는데 도움이 됐다.

그 알고리즘을 살펴보면, 각 정점에 대해서 DFS트리를 만들면서, 다음 두가지를 기록한다.

1. 해당 정점을 방문한 순서: 이를 ord이라고 하자.
2. 해당 정점을 루트로 하는 서브트리로 부터 연결된 정점중 가장 작은 ord 값: 이를 low라고 하자.

그다음 해당 정점을 리턴하기전에 ord와 low를 비교해서 low가 ord보다 작으면 우회경로가 존재하므로 단절점이 아닌것으로 판단.

예를 들어 아래와 같은 그래프가 있을때

먼저 DFS트리를 그려보면 다음과 같다.(트리는 방향그래프가 아니나 이해를 위해 방향그래프로 표했다. 역방향 화살표가 하나있는데 이는 물론 트리의 구성요소는 아니고 back edge이다.)
괄호안의 숫자두개는 (ord, low)가 된다.
edge(u, v)가 아래방향 화살표인 tree edge라면, low[u] = min(low[u], low[v])가 되고,
edge(u, v)가 위쪽방향 화살표인 back edge라면, low[u] = min(low[u], ord[v])가 된다.
(이규칙에 맞는지 위의 그림을 잘 살펴보자)

말단노드가 아니면서 ord <= low 이면 단절점이므로 위 그래프에서는 단절점은 1, 6, 7이다.
(루트의 경우는 자식 노드가 2개 이상인지로 별도 판단)

근데, 실제로는 ord[n], low[n]을 다 구한다음에 후처리로 단절점을 판단하면 아래와 같은 반례때문에 잘되지 않았다(4번 노드가 문제인데 low[4]값은 최종적으로 1이 된다. 그러므로 후발적으로 ord <= low를 판단하면 단절점이 아닌것으로 판단된다)
그래서 low[n]을 최종판단하기전에 중간과정에서 자식노드중 하나라도 ord <= 자식트리의 low 인 순간에 즉발적으로 단절점을 판단해줘야했다. 자세한 사항은 아래 코드를 참조하자.이 문제의 답안이기도 하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int V,E;cin>>V>>E;
    vvi adj_list(V + 1);
    REP(i, E)
    {
        int A,B;cin>>A>>B;
        adj_list[A].push_back(B);
        adj_list[B].push_back(A);
    }
    set<int> ans;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi visit(V + 1), ord(V + 1), parent(V + 1), root(V + 1); int g_ix = 0;
    function<int(intint)> dfs = [&](int n, int par)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        int child = 0;
        for (auto adj : adj_list[n])
        {
            if (adj == par) continue;
            if (visit[adj])  // 백엣지의 경우
                low = min(low, ord[adj]);  // 접근가능한 back정점의 순서로 업데이트
            else {  // 트리엣지의 경우
                child++;
                int r = dfs(adj, n);  
                // 루트가 아니고 자식트리중 하나라도 자신위로 올라가지 못하면
                if(par!=-1 && r>=ord[n])  
                {
                    // 전체 자식노드를 보는게 아니라 즉발기로 동작함에 유의
                    // 주의할점은 현재 정점의 low값을 최종결정하기전에
                    // 단절점 판정이 이루어지는 부분
                    ans.insert(n);
                }
                low = min(low, r);
            }
        }
        // 루트이고 자식이 2개이상이면
        if (par == -1 && child > 1) ans.insert(n);
        return low;
    };
    REP1(i, V)if (visit[i] == 0)dfs(i, -1), root[i] = 1;
    cout << (int)ans.size() << endl
    for (auto a : ans) cout << a << ' ';
    cout << endl;
    return 0;
}
cs



단절선

단절점 소스코드와 개념을 거의 그대로 활용할 수 있고, 아래 두가지 부분만 다르다.
1. 루트노드란 개념이 사라진다.
2. r >= ord[n] 조건이 r>ord[n] 으로 등호가 하나 사라진다.

2번에 대해서는 예제 입력인 아래 그래프에서  1번(루트) 정점을 기준으로 생각하면 등호인경우 사이클이 생겨서 단절선이 아님을 확인할 수 있다.(아래 그림 참조)
여기를 보면 해당 고민을 나보다 깊게 한 다른 블로그 포스팅을 볼 수 있다.

소스코드는 아래와 같고, 이 문제의 답안이기도 하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1);
    REP(i, E)
    {
        int A, B; cin >> A >> B;
        adj_list[A].push_back(B);
        adj_list[B].push_back(A);
    }
    set<pair<intint>> ans;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi visit(V + 1), ord(V + 1), parent(V + 1), root(V + 1); int g_ix = 0;
    function<int(intint)> dfs = [&](int n, int par)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        for (auto adj : adj_list[n])
        {
            if (adj == par) continue;
            if (visit[adj])  // 백엣지의 경우
                low = min(low, ord[adj]);  // 접근가능한 백정점 순서로 업데이트
            else {  // 트리엣지의 경우
                int r = dfs(adj, n);
                // 자식트리중 하나라도 자신위로 올라가지 못하면
                if (r > ord[n])  // 단절점 케이스와 다르게 r == ord[n]인 경우 그려보면 사이클로 인해 단절선이 아님을 알 수 있다.
                {
                    // 전체 자식노드를 보는게 아니라 즉발기로 동작함에 유의
                    // 주의할점은 현재 정점의 low값을 최종결정하기전에
                    // 단절점 판정이 이루어지는 부분
                    ans.insert({ min(n,adj), max(n,adj) });  // 문제 조건에 따라 순서 조정
                }
                low = min(low, r);
            }
        }
        // 단절선에서 루트정점이란 개념은 빠진다.
        // if (par == -1 && child > 1) ans.insert(n);
        return low;
    };
    REP1(i, V)if (visit[i] == 0)dfs(i, -1), root[i] = 1;
    cout << (int)ans.size() << '\n';
    for (auto a : ans) cout << a.first << ' ' << a.second << '\n';
    return 0;
}
cs


반응형


개념

SCC는 방향그래프 내에서 서브사이클을 이루는 집단들을 의미한다. 따라서 개념적으로는 강한연결요소라는 용어보다 강한연결집합이라는 용어가 더 적절해보이긴한다.

자세한 설명은 여기, 여기, 여기를 참조하면 개념에 대해서 어렵지 않게 파악 가능하다.

동작하는 원리에 대해 궁금하면 여기에 설명이 잘 나와있다.

활용도와 의의에 대해서는 여기에 잘 나와있다.


SCC를 구하는 알고리즘에는 크게 코사라주와 타잔이 있다.


코사라주(Kosaraju) 알고리즘

코사라주는 DFS두번 돌리면서 구하는 방법이고 여기, 여기를 보면 설명이 잘 돼있어서 쉽게 이해 가능하다. 

구현도 그냥 이해한 대로 술술 하면 되는 수준이었다.

왜 그런지 증명은 정확히 모르겠고 HOW는 파악이 어렵지 않다.

아래는 내가 직접 구현해본 코드이고, 이 문제의 답안이기도 하다.

dfs함수에서 마지막에 스택push하는 걸 보면 위상정렬개념이 들어간다는 사실을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
 
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(V + 1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (auto a : adj_list[n]) dfs(a);
        S.push(n);
    };
    REP1(i, V) if (visit[i] == 0) dfs(i);
 
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(V + 1); vvi ans;
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi ans2;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            ans2.push_back(n);
            for (auto a : adj_list2[n])    dfs(a);
        };
        dfs(n);
        sort(ALL(ans2));
        ans.push_back(ans2);
    }
    sort(ALL(ans));
    cout << ans.size() << endl;
    REP(i, SZ(ans))    {
        REP(j, SZ(ans[i])) cout << ans[i][j] << ' ';
        cout << -1 << endl;
    }
 
    return 0;
}
cs


타잔(Tarjan) 알고리즘

타잔 알고리즘은 생각보다 이해하기가 빡시다. 한가지 알아둘 것은 타잔 알고리즘이 SCC구할때 쓰는 알고리즘만 칭하는게 아니라, 여기서 쓰는 테크닉과 비슷하면 타잔이라고 부르는 것 같다는 점이다(타잔류?). 이건 확인은 필요


타잔의 경우, 결과값으로 SCC위상정렬까지 얻을 수 있어서, 이후 활용도에서 더 편하다.


타잔 알고리즘을 이해하려면, 먼저 트리 간선(tree edge), 순방향 간선(forward edge),역방향 간선(backward edge),교차 간선(cross edge)등 그래프 간선의 종류를 이해해야 한다.

그다음 단절선에 대한 이해를 해야한다. 그다음 여기 설명을 보면 이해하고 구현하기 좋다.


SCC타잔 알고리즘이 단절선 로직과 다른점은 다음과 같다.

1. 단절선 로직은 자식트리중 하나라도 현재간선보다 위로 못올라가면 바로, 단절선으로 판정하지만 SCC타잔에서는 전체 자식트리를 다 보고나서, 모든  자식트리가 현재간선보다 위로 못올라가면 SCC로 판정한다.

2. 단절선 로직과 다르게 스택을 운용하며, 처음 진입시 스택에 넣고 위의 1번 SCC판정조건이 만족되면 현재 정점까지 팝한다.

3. 단절선 로직은 visit배열만 사용하는데 반해서, SCC타잔은 finish배열도 추가적으로 사용한다. (물론 두 알고리즘 모두  visit배열대신 ord로 대체는 가능)

4. 단절선 로직은 tree-edge, back-edge만 고려하는데 반해서 SCC타잔은 추가적으로 cross-edge도 고려한다. (forward-edge는 둘다 무시)


단절선 코드를 변경해서 내가 구현해본 코드는 다음과 같다. 위와 같은 문제에 대한 답이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1);
    REP(i, E)
    {
        int A, B; cin >> A >> B;
        adj_list[A].push_back(B);
    }
    vvi ans;
    stack<int> S;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi visit(V + 1), ord(V + 1), parent(V + 1); int g_ix = 0;
    // 코라사주나 단절선 구하는것과 다르게 finish 운영해줌
    // 일반적으로 finish배열이 dfs리턴할때 true해주는것과 다르게
    // SCC분리가 끝났음을 의미
    vi finish(V + 1);
    function<int(int)> dfs = [&](int n)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        S.push(n);  // 스택에 먼저 푸시
        for (auto adj : adj_list[n])
        {
            //if (adj == par) continue;  // SCC는 방향그래프로 주어지므로 parent개념은 없다.
            if (visit[adj] == 0)  // tree edge 의 경우
            {
                int r = dfs(adj);
                // 단절점 로직의 경우 여기서 자식트리중 하나라도 자신위로 올라가지 못하면 단절점으로 판정하지만
                // SCC 타잔에서는 그러한 로직은 없고, 아래에 result == ord[n] 으로
                // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출하는 로직으로 바뀐다.
                // if (r > ord[n]) ans.insert({ min(n,adj), max(n,adj) });
                low = min(low, r);
            }
            // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
            else if (finish[adj]==0)  // back edge 또는 cross edge의 일부
                low = min(low, ord[adj]);  // 접근가능한 백정점 순서로 업데이트
        }
        // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출
        if (low == ord[n])
        {
            vi scc;
            while(S.size())
            {
                int a = S.top(); S.pop();
                scc.push_back(a);
                finish[a] = 1;
                if (a == n) break;
            }
            sort(scc.begin(), scc.end());
            ans.push_back(scc);
        }
        
        return low;
    };
    REP1(i, V)if (visit[i] == 0)dfs(i);
    sort(ans.begin(), ans.end());
    cout << (int)ans.size() << '\n';;
    for(auto a:ans)
    {
        for (auto b : a) cout << b << ' ';
        cout << -1 << '\n';;
    }
    return 0;
}
cs



반응형

문제는 여기


특정간선을 포함하는경우, 실제 MST보다 큰 값이 나올 수 있다. (프루스칼로 MST를 구할때는 간선을 정렬한다음에 최소간선부터 시작함을 상기하자)

MST 한 번 하는데 $O(E \times log E)$ 니까, 간선개수만큼 하면 $O(E^2 \times log E)$ 일거고.. E가 10^5보다 크므로 나이브하게 해서는 TLE확정이다.


풀이방법

MST를 구한다음에.. 해당 간선이 이미 포함돼 있으면 MST값을 그냥 찍으면 되고, 만약 포함되어 있지 않으면 포함시키고, 다른 간선중 하나를 빼는식으로 하면 된다.

잘 이해가 가지 않는다면 다음 그래프를 보자. (간선 가중치는 생략돼 있지만 MST를 그린 화면으로 생각하자)

여기서 만약 정점 1과 정점4를 잇는 간선을 포함한 답을 구한다고 생각해보자. (위그림에서는 정점1과 정점4 사이에 간선이 없지만 원래는 있었는데 MST구하면서 제거됐다고 가정)

위 그림에서 알 수 있듯이 MST에 (1,4)간선을 추가한 순간 사이클이 생기기 때문에, (1,6) (6,2) (2,5) (5,3) (3,4) 중 하나를 대신 끊어줘야 한다.

이때 나이브하게 경로를 쭉 따라가면서 가중치 가장 큰 걸 빼주는 식으로 하면, 그래프 구조가 직선적인 경우 O(E)가 걸리게 되어 E개의 쿼리를 처리하는데 O(E^2)이 걸려서 TLE가 나게된다.

따라서 위에 LCA로 표시했지만 공통조상까지 올라가고, 내려오는 경로상에서 스파스 테이블을 사용해서 효율적으로 최대가중치를 가진간선을 골라줘야 한다. 참고로 LCA에서 최대가중치 간선을 고르는 문제는 여기에 있다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
const int INF = (int)1e9;
const int MAXN = 200001;
const int LOG_N = 19;
 
struct node3
{
    int u, v, w;
    bool operator < (const node3& t) const {
        return w < t.w;
    }
};
struct node2 { int v, w; };
bool operator<(node2 l, node2 r) { return l.w > r.w; }
vector<vector<node2>> adj_list(MAXN);
 
ll MST_Kruskal(int max_v, vector<node3> v) {
    struct union_find {
        vector<int> parent;
        union_find(int n) {
            parent.resize(n + 1);
            for (int i = 0; i <= n; i++) parent[i] = i;
        }
        int find(int v) {
            return v == parent[v] ? v : parent[v] = find(parent[v]);
        }
        bool uni(int u, int v) {
            u = find(u), v = find(v);
            if (u == v) return 0;
            parent[u] = v;
            return 1;
        }
    };
    union_find uf(max_v);
    sort(v.begin(), v.end());
    ll ans = 0;
    for (auto a : v) {
        if (uf.uni(a.u, a.v)) {
            adj_list[a.u].push_back({ a.v,a.w });
            adj_list[a.v].push_back({ a.u,a.w });
            ans += a.w;
        }
    }
    return ans;
}
 
 
//무방향그래프를 인풋으로 받아, 트리로 만들어준다.LCA를 위한 작업도 해준다.
struct result { int root; int max_level; };
vi parent(MAXN), level(MAXN), dist2(MAXN);
// ancestor[y][x] :: x의 2^y번째 조상을 의미
vvi ancestor(LOG_N + 1, vi(MAXN, -INF));  
 
result treefy(vector<vector<node2>>& adj_list, int root=-1,bool base1=false) {
    int max_v = (int)adj_list.size();
    int max_level = LOG_N;
    function<void(node2, intint)> dfs = [&](node2 n, int par, int lv) {
        parent[n.v] = par, level[n.v] = lv, dist2[n.v] = n.w;
        ancestor[0][n.v] = par;  // 첫번째(2^0) 조상은 부모
        for (auto adj : adj_list[n.v]) {
            if (adj.v == par) continue;  // 부모방향 간선제거
            dfs(adj, n.v, lv + 1);
        }
    };
    dfs({ root,0 }, -INF, 1);
    for (int i = 1; i <= max_level; i++) {
        for (int j = 1; j < max_v; j++) {
            int tmp = ancestor[i - 1][j];
            if (tmp == -INF) continue;
            ancestor[i][j] = ancestor[i - 1][tmp];
        }
    }
 
    return { root, max_level };
}
 
int lca(int u, int v, vi& level, vvi& ancestor)
{
    if (level[u] < level[v]) swap(u, v);  // b가 더 깊도록 조정
 
    int diff = level[u] - level[v];
    for (int i = 0; diff; i++) {
        if (diff & 1) u = ancestor[i][u];  //b를 올려서 level을 맞춘다.
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = LOG_N; i >= 0; i--) {
        // a와 b가 다르다면 현재 깊이가 같으니, 깊이를 a,b동시에 계속 올려준다.
        if (ancestor[i][u] != ancestor[i][v]) 
            u = ancestor[i][u], v = ancestor[i][v];
    }
    return ancestor[0][u];
 
 
}
 
int N, M, u, v, w;
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); 
    cin >> N >> M;
    vector<node3> vv;
    for(int i=0;i<M;i++) {
        cin >> u >> v >> w;
        vv.push_back({ u,v,w });
    }
    auto mst = MST_Kruskal(N, vv);
 
    result r = treefy(adj_list, 1true);
    vector<vector<int>> max_dp(r.max_level + 1vector<int>(N + 10));
    for (int i = 1; i <= N; i++) max_dp[0][i] = dist2[i];
    for (int jump = 1; jump <= r.max_level; jump++)
    {
        for (int here = 1; here <= N; here++)
        {
            int tmp = ancestor[jump - 1][here];
            if (tmp == -INF) continue;
            max_dp[jump][here] = 
                max(max_dp[jump - 1][here], max_dp[jump - 1][tmp]);
        }
    }
 
    for(int i=0;i<M;i++)
    {
        auto [s, e, w] = vv[i];
        int l = lca(s, e, level, ancestor);
 
        int mx = -1;
        int diff = level[s] - level[l];
        for (int j = 0; diff; j++) {
            if (diff & 1) mx = max(mx, max_dp[j][s]), s = ancestor[j][s];
            diff >>= 1;
        }
        diff = level[e] - level[l];
        for (int j = 0; diff; j++) {
            if (diff & 1) mx = max(mx, max_dp[j][e]), e = ancestor[j][e];
            diff >>= 1;
        }
 
        cout << mst + w - mx << '\n';
    }
 
    return 0;
}
cs










반응형

'Programming > Problem Solving' 카테고리의 다른 글

double과 관련된 핸들링  (0) 2021.12.26
백준 4103 ATM  (0) 2020.05.05
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05

여기, 여기, 여기를 보면 기본 개념에 대해서는 얼추 파악할 수 있다.

LCA를 구할때 쓰는 Binary Lifting도 sparse table의 일종이다.

기본 개념은 O(N)걸리는 쿼리를 전처리 작업을 통해서 O(log N)이나 O(1)로 줄인다고 하는것

그걸 위해서 A[N] 이란게 있다고 하면 ST[log2(N)][N] 이런 스케일로 테이블 정의하고..

ST[0][N] = A[N]으로 초기화 한다음에

REP1(i, max_level)REP(j,N) ST[i][j] = ST[i-1][어쩌구]..저쩌구 이런식으로 한다.

i가 1증가할때 마다 2배씩 뛰는건데 자세한건 위의 링크를 참조하자.


기본LCA문제를 풀 때에도 ancestor 만들때 위의 기술을 사용하고,

단순히 합성함수를 효율적으로 구하는 문제에서도 사용된다.

트리 정점 a, b의 경로에서 가장 가중치 큰거나 작은거 하나 출력하는 문제에서도 사용되고,

a,b경로중 k번째 정점을 찾는 문제에서도 사용된다.


아직 나도 통달한건 아니라 이정도로 기록해둔다.

반응형

여기보면 개념자체는 간단한다.


$O(N)$ 나이브 구현

더깊은 애부터 하나씩 올려서 만나는데 까지 해보는 방식으로 해보면 된다.

구현도 트리로 인한 복잡성은 약간 있지만, 나이브한 편이고 내가 구현해본 건 다음과 같다. 이 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
const int INF = (int)1e9;
 
 
//무방향그래프를 인풋으로 받아, 특정 정점을 루트를 가지는 방향그래프(트리)로 만들어준다.
struct result { vector<vi> tree; int root; vi parent, level; };
result treefy(vector<vi>& adj_list, int root = -1bool base1 = false) {
    int max_v = (int)adj_list.size();
    vector<vi> tree(max_v);
    if (root == -1)
    {
        //find root(왼쪽이 parent인경우만 성립)
        map<intint> m;
        for (int i = (int)base1; i < max_v; i++)
            for (auto a : adj_list[i]) m[a]++;
        for (int i = (int)base1; i < max_v; i++)
            if (m[i] == 0) { root = i; break; }
    }
    vi parent(max_v), level(max_v);
    function<void(intintint)> dfs = [&](int node, int par, int lv) {
        parent[node] = par, level[node] = lv;
        for (auto adj : adj_list[node]) {
            if (adj == par) continue;  // 부모방향 간선제거
            tree[node].push_back(adj);
            dfs(adj, node, lv + 1);
        }
    };
    dfs(root, -INF, 1);
 
    return { tree, root, parent, level };
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin>>T;while(T--){
        int N;cin>>N;
        vvi adj_list(N + 1);
        REP(i,N - 1)
        {
            int u,v;cin>>u>>v; adj_list[u].push_back(v);
        }
        result r = treefy(adj_list, -1true);
        int a,b;cin>>a>>b;
        if (r.level[a] > r.level[b]) swap(a, b);
        while (r.level[a] < r.level[b]) b = r.parent[b];
        while (a != b) a = r.parent[a], b = r.parent[b];
        cout << (a) << '\n';
    }
 
    return 0;
}
cs


$O(log N)$ 구현 (쿼리 형태면 $O(M \times log N)$)

역시 여기를 보면 과정을 이해하기 쉽도록 설명되어 있다. 다만, 그 구현과정에서 실수가 들어가기 쉬운데, 이건 내가 직접 구현하기보다 구현되어 있는걸 가져다 쓰는 형식이 좋을 것 같다. 내 라이브러리와 합쳐진 버전은 다음과 같다.

이 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = (int)1e9;
 
//무방향그래프를 인풋으로 받아, 트리로 만들어준다.LCA를 위한 작업도 해준다.
struct result {vvi tree;int root;vi parent,level; int max_level;vvi ancestor;};
result treefy(vector<vi>& adj_list, int root = -1bool base1 = false) {
    int max_v = (int)adj_list.size();
    vector<vi> tree(max_v);
    if (root == -1)
    {
        // find root(왼쪽이 parent인경우만 성립하는듯, 안그러면 root가 여러개다)
        map<intint> m;
        for (int i = (int)base1; i < max_v; i++)
            for (auto a : adj_list[i]) m[a]++;
        for (int i = (int)base1; i < max_v; i++)
            if (m[i] == 0) { root = i; break; }
    }
    vi parent(max_v), level(max_v);
    int max_level = (int)floor(log2(max_v));
    // ac[y][x] :: x의 2^y번째 조상을 의미
    vvi ac(max_level + 1, vi(max_v, -INF));
    function<void(intintint)> dfs = [&](int node, int par, int lv) {
        parent[node] = par, level[node] = lv;
        ac[0][node] = par;  // 첫번째(2^0) 조상은 부모
        for (auto adj : adj_list[node]) {
            if (adj == par) continue;  // 부모방향 간선제거
            tree[node].push_back(adj);
            dfs(adj, node, lv + 1);
        }
    };
    dfs(root, -INF, 1);
    for (int i = 1; i <= max_level; i++) {
        for (int j = 1; j < max_v; j++) {
            int tmp = ac[i - 1][j];
            if (tmp == -INF) continue;
            ac[i][j] = ac[i - 1][tmp];
        }
    }
 
    return { tree, root, parent, level,max_level, ac };
}
 
int lca(int u, int v, int max_level, vi& level, vvi& ancestor)
{
    if (level[u] < level[v]) swap(u, v);  // b가 더 깊도록 조정
    int diff = level[u] - level[v];
    for (int i = 0; diff; i++) {
        if (diff & 1) u = ancestor[i][u];  //b를 올려서 level을 맞춘다.
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = max_level; i >= 0; i--) {
        // a와 b가 다르다면 현재 깊이가 같으니, 깊이를 a,b동시에 계속 올려준다.
        if (ancestor[i][u] != ancestor[i][v]) 
            u = ancestor[i][u], v = ancestor[i][v];
    }
    return ancestor[0][u];
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    int N; cin >> N; vvi adj_list(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    result r = treefy(adj_list, 1true);
    int m; cin >> m; for (int z = 0; z < m; z++)
    {
        int a, b; cin >> a >> b;
        int ans = lca(a, b, r.max_level, r.level, r.ancestor);
        cout << (ans) << '\n';
    }
    return 0;
}
cs




반응형

여기참조

 

유향그래프가 있을 때, 오더링 하는 방법론에 대한게 위상정렬이고, 

DFS를 이용한 방법(DFS Spanning Tree)과

Queue를 이용한 방법(indgree)이 있다. 나한테는 이방식이 편했다.

위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(DAG)여야 한다.

 

사이클이 있는 경우는 오더링이 불가 하고, DFS와 Queue모두 이를 중간 과정을 통해 디텍트 할 수 있다.

 

위키피디아의 다음 설명을 읽어보자

위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 

그렇다면 위상정렬과 DAG과의 관계는 무엇인가.. 위상정렬이 가능하려면 (사이클이 없는) DAG이어야 한다고 말할 수 있다.

 

위상정렬에 대한 풀어보면 좋은 문제는 다음과 같다.

 

백준 ACM Craft : 바닐라 한데, 제약조건이 좀 빡빡하다(100,000이라 adjacent matrix 사용 불가)

 

 

BFS방식

여기 예제를 통한 설명 좋다.

일반 BFS와의 차이점은 사이클 처리를 위해서 while(q.empty()==false) 이걸로 루프돌리는게 아니라,

for(int i=0;i<N;i++) 이걸로 루프돌리는게 특이하고, 인접리스트와 별도로 in-edge카운팅해줘서 0이되는것만 enqueue하면 된다.

아래는 내가 구현하고 이 문제로 검증한 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
#define OUT(x) {cout << (x) << '\n'; }
#define IN(n) int n;cin>>n
 
int32_t main()
{
    FastIO; IN(N); IN(M);
    vi in(N + 1); // in-edge를 관리해주는게 핵심
    vvi adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        IN(u); IN(v); adj_list[u].push_back(v); in[v]++;
    }
    queue<int> q;
    function<void(int n)> enqueue = [&](int n) {
        if ((in[n]--> 0return;
        q.push(n);
    };
    vi ans;
    REP1(i, N) enqueue(i);
    while (N--) {  // 정확히 n번 dequeue로 끝난다.
        if (!q.size()) { break; }//cycle!
        int n = q.front(); q.pop();
        ans.push_back(n);
        for (auto adj : adj_list[n]) {
            enqueue(adj);
        }
    }
    for (auto a : ans) cout << a << ' ';
    return 0;
}
cs

 

 

DFS방식

BFS방식이 좀 더 직관적이긴 하지만, DFS방식은 DP연계가 쉽다는 점에서 알아둘 필요가 있다.
DFS방식은 말하자면 다음과 같다.
DFS로 방문할 수 있는 모든 노드를 재귀적으로 방문한뒤..
방문할 수 있는 next가 없으면
topological_sort 와 같은 큐에 데이터를 집어넣고, 이를 역순으로 표시
여기를 보면 알기 쉽게 설명돼있다. 위의 BFS버전과 같은 문제에 대한 답안이기도 하다.
DFS의 경우는 in-edge관리를 안해줘도 돼서 어떻게 보면 훨씬 더 다루기 쉽다. (사이클 처리는 대신 약간 복잡)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
struct result { bool cycle; vi sorted; };
result topological_sort(int max_v, int start_v, vvi& adj_list, bool base1=false) {
    if (base1) max_v++;
    // cycle 검출을 위해 finish배열 하나더 기용해준다.
    // visit되고 finish되기전에 다시 방문되면 사이클로 보는것
    vi visit(max_v), finish(max_v);
    result r = { false, vi() };
    deque<int> sorted; bool cycle = false;
    function<void(int)> dfs = [&](int v) {
        visit[v] = 1;
        for (auto adj : adj_list[v]) {
            if (visit[adj] == 0) dfs(adj);
            else if (finish[adj] == 0) {
                cycle = 1;// visit은 1인데, finish 는 0으로 들어왔다? cycle!
            }
        }
        finish[v] = 1;
        sorted.push_front(v);
    };
    if (start_v == -1) {
        for (int i = (int)base1; i < max_v; i++
            if (visit[i] == 0) dfs(i);
    }
    else dfs(start_v);
    return { cycle, vi(sorted.begin(), sorted.end()) };
}
 
int32_t main()
{
    int N, M; cin >> N >> M;
    //vi in(N + 1);  // DFS버전에서는 in-edge관리를 안해도 된다.
    vvi adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v; adj_list[u].push_back(v);
    }
 
    // 일단 아이디어는 DFS돌려서 말단까지 가고,
    // 거기서 부터 stack에 넣어주면 위상정렬 정순위가 된다는것.
    result r = topological_sort(N, -1, adj_list, true);
    for (auto a : r.sorted) cout << a << ' ';
    return 0;
}
cs
그런데, visit, finish 처리를 위처럼 하면 경로 카운팅 문제에서는 문제가 생긴다.
예를 들어 1번 정점에서 2번 정점으로의 경로가 하나가 아니라 여러개인경우,
visit만 1인상태에서 finish전에 여러경로를 다 세주어야 하는데,
if (visit[adj] == 0) dfs(adj) 이부분 때문에 하나의 경로만 카운팅 되는 것
 

 

 

반응형

'Programming > Algorithm' 카테고리의 다른 글

스파스 테이블(Sparse Table), Binary Lifting  (0) 2020.05.01
공통조상(LCA, Lowest Common Ancestor) 알고리즘  (0) 2020.04.29
트라이(Trie)  (0) 2020.04.22
KMP( Knuth, Morris, Prett)  (0) 2020.04.20
기하  (0) 2020.04.19

+ Recent posts