17_scc.cpp

Download
cpp 445 lines 11.7 KB 
  1/*
  2 * ๊ฐ•ํ•œ ์—ฐ๊ฒฐ ์š”์†Œ (Strongly Connected Components)
  3 * Tarjan, Kosaraju, 2-SAT
  4 *
  5 * ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„์—์„œ ์„œ๋กœ ๋„๋‹ฌ ๊ฐ€๋Šฅํ•œ ์ •์ ๋“ค์˜ ์ง‘ํ•ฉ์„ ์ฐพ์Šต๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <stack>
 11#include <algorithm>
 12
 13using namespace std;
 14
 15// =============================================================================
 16// 1. Tarjan's Algorithm
 17// =============================================================================
 18
 19class TarjanSCC {
 20private:
 21    int n;
 22    vector<vector<int>> adj;
 23    vector<int> ids;
 24    vector<int> low;
 25    vector<bool> onStack;
 26    stack<int> st;
 27    int counter;
 28    int sccCount;
 29    vector<vector<int>> sccs;
 30
 31    void dfs(int v) {
 32        ids[v] = low[v] = counter++;
 33        st.push(v);
 34        onStack[v] = true;
 35
 36        for (int u : adj[v]) {
 37            if (ids[u] == -1) {
 38                dfs(u);
 39                low[v] = min(low[v], low[u]);
 40            } else if (onStack[u]) {
 41                low[v] = min(low[v], ids[u]);
 42            }
 43        }
 44
 45        // SCC์˜ ๋ฃจํŠธ์ธ ๊ฒฝ์šฐ
 46        if (ids[v] == low[v]) {
 47            vector<int> scc;
 48            while (true) {
 49                int u = st.top();
 50                st.pop();
 51                onStack[u] = false;
 52                scc.push_back(u);
 53                if (u == v) break;
 54            }
 55            sccs.push_back(scc);
 56            sccCount++;
 57        }
 58    }
 59
 60public:
 61    TarjanSCC(int n, const vector<vector<int>>& adj) : n(n), adj(adj) {
 62        ids.assign(n, -1);
 63        low.assign(n, 0);
 64        onStack.assign(n, false);
 65        counter = 0;
 66        sccCount = 0;
 67
 68        for (int i = 0; i < n; i++) {
 69            if (ids[i] == -1) {
 70                dfs(i);
 71            }
 72        }
 73    }
 74
 75    int getSCCCount() const { return sccCount; }
 76    const vector<vector<int>>& getSCCs() const { return sccs; }
 77
 78    // SCC ์ถ•์•ฝ ๊ทธ๋ž˜ํ”„ (DAG)
 79    vector<vector<int>> getCondensedGraph() {
 80        vector<int> sccId(n);
 81        for (int i = 0; i < (int)sccs.size(); i++) {
 82            for (int v : sccs[i]) {
 83                sccId[v] = i;
 84            }
 85        }
 86
 87        set<pair<int, int>> edges;
 88        for (int v = 0; v < n; v++) {
 89            for (int u : adj[v]) {
 90                if (sccId[v] != sccId[u]) {
 91                    edges.insert({sccId[v], sccId[u]});
 92                }
 93            }
 94        }
 95
 96        vector<vector<int>> dag(sccCount);
 97        for (auto [u, v] : edges) {
 98            dag[u].push_back(v);
 99        }
100
101        return dag;
102    }
103};
104
105// =============================================================================
106// 2. Kosaraju's Algorithm
107// =============================================================================
108
109class KosarajuSCC {
110private:
111    int n;
112    vector<vector<int>> adj;
113    vector<vector<int>> radj;  // ์—ญ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„
114    vector<bool> visited;
115    vector<int> order;         // ์ฒซ ๋ฒˆ์งธ DFS ์ˆœ์„œ
116    vector<vector<int>> sccs;
117
118    void dfs1(int v) {
119        visited[v] = true;
120        for (int u : adj[v]) {
121            if (!visited[u]) {
122                dfs1(u);
123            }
124        }
125        order.push_back(v);
126    }
127
128    void dfs2(int v, vector<int>& scc) {
129        visited[v] = true;
130        scc.push_back(v);
131        for (int u : radj[v]) {
132            if (!visited[u]) {
133                dfs2(u, scc);
134            }
135        }
136    }
137
138public:
139    KosarajuSCC(int n, const vector<vector<int>>& adj) : n(n), adj(adj), radj(n) {
140        // ์—ญ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ ์ƒ์„ฑ
141        for (int v = 0; v < n; v++) {
142            for (int u : adj[v]) {
143                radj[u].push_back(v);
144            }
145        }
146
147        // ์ฒซ ๋ฒˆ์งธ DFS: ์ข…๋ฃŒ ์ˆœ์„œ
148        visited.assign(n, false);
149        for (int i = 0; i < n; i++) {
150            if (!visited[i]) {
151                dfs1(i);
152            }
153        }
154
155        // ๋‘ ๋ฒˆ์งธ DFS: SCC ์ฐพ๊ธฐ
156        visited.assign(n, false);
157        for (int i = n - 1; i >= 0; i--) {
158            int v = order[i];
159            if (!visited[v]) {
160                vector<int> scc;
161                dfs2(v, scc);
162                sccs.push_back(scc);
163            }
164        }
165    }
166
167    int getSCCCount() const { return sccs.size(); }
168    const vector<vector<int>>& getSCCs() const { return sccs; }
169};
170
171// =============================================================================
172// 3. 2-SAT
173// =============================================================================
174
175class TwoSAT {
176private:
177    int n;
178    vector<vector<int>> adj;
179    vector<int> sccId;
180    vector<bool> assignment;
181
182    int var(int x) { return x >= 0 ? 2 * x : 2 * (-x - 1) + 1; }
183    int notVar(int x) { return x >= 0 ? 2 * x + 1 : 2 * (-x - 1); }
184
185public:
186    TwoSAT(int n) : n(n), adj(2 * n), sccId(2 * n), assignment(n) {}
187
188    // x โˆจ y ์ถ”๊ฐ€ (๋‘˜ ์ค‘ ํ•˜๋‚˜๋Š” ์ฐธ)
189    void addClause(int x, int y) {
190        // ยฌx โ†’ y, ยฌy โ†’ x
191        adj[notVar(x)].push_back(var(y));
192        adj[notVar(y)].push_back(var(x));
193    }
194
195    // x๋ฅผ ์ฐธ์œผ๋กœ ๊ฐ•์ œ
196    void setTrue(int x) {
197        adj[notVar(x)].push_back(var(x));
198    }
199
200    // x๋ฅผ ๊ฑฐ์ง“์œผ๋กœ ๊ฐ•์ œ
201    void setFalse(int x) {
202        adj[var(x)].push_back(notVar(x));
203    }
204
205    // x โŠ• y (์ •ํ™•ํžˆ ํ•˜๋‚˜๋งŒ ์ฐธ)
206    void addXor(int x, int y) {
207        addClause(x, y);
208        addClause(-x - 1, -y - 1);
209    }
210
211    bool solve() {
212        TarjanSCC scc(2 * n, adj);
213        auto sccs = scc.getSCCs();
214
215        // SCC ID ํ• ๋‹น
216        for (int i = 0; i < (int)sccs.size(); i++) {
217            for (int v : sccs[i]) {
218                sccId[v] = i;
219            }
220        }
221
222        // ์ถฉ์กฑ ๊ฐ€๋Šฅ์„ฑ ๊ฒ€์‚ฌ
223        for (int i = 0; i < n; i++) {
224            if (sccId[2 * i] == sccId[2 * i + 1]) {
225                return false;  // x์™€ ยฌx๊ฐ€ ๊ฐ™์€ SCC
226            }
227            // SCC ์ˆœ์„œ๊ฐ€ ์—ญ๋ฐฉํ–ฅ์ด๋ฏ€๋กœ ๋น„๊ต
228            assignment[i] = sccId[2 * i] > sccId[2 * i + 1];
229        }
230
231        return true;
232    }
233
234    vector<bool> getAssignment() const { return assignment; }
235};
236
237// =============================================================================
238// 4. ์ ˆ๋‹จ์  (Articulation Points)
239// =============================================================================
240
241class ArticulationPoints {
242private:
243    int n;
244    vector<vector<int>> adj;
245    vector<int> ids, low;
246    vector<bool> isAP;
247    int counter;
248
249    void dfs(int v, int parent) {
250        ids[v] = low[v] = counter++;
251        int children = 0;
252
253        for (int u : adj[v]) {
254            if (ids[u] == -1) {
255                children++;
256                dfs(u, v);
257                low[v] = min(low[v], low[u]);
258
259                if (parent != -1 && low[u] >= ids[v]) {
260                    isAP[v] = true;
261                }
262            } else if (u != parent) {
263                low[v] = min(low[v], ids[u]);
264            }
265        }
266
267        // ๋ฃจํŠธ๊ฐ€ 2๊ฐœ ์ด์ƒ์˜ ์ž์‹์„ ๊ฐ€์ง€๋ฉด ์ ˆ๋‹จ์ 
268        if (parent == -1 && children > 1) {
269            isAP[v] = true;
270        }
271    }
272
273public:
274    ArticulationPoints(int n, const vector<vector<int>>& adj) : n(n), adj(adj) {
275        ids.assign(n, -1);
276        low.assign(n, 0);
277        isAP.assign(n, false);
278        counter = 0;
279
280        for (int i = 0; i < n; i++) {
281            if (ids[i] == -1) {
282                dfs(i, -1);
283            }
284        }
285    }
286
287    vector<int> getArticulationPoints() {
288        vector<int> result;
289        for (int i = 0; i < n; i++) {
290            if (isAP[i]) result.push_back(i);
291        }
292        return result;
293    }
294};
295
296// =============================================================================
297// 5. ๋ธŒ๋ฆฟ์ง€ (Bridges)
298// =============================================================================
299
300class Bridges {
301private:
302    int n;
303    vector<vector<int>> adj;
304    vector<int> ids, low;
305    vector<pair<int, int>> bridges;
306    int counter;
307
308    void dfs(int v, int parent) {
309        ids[v] = low[v] = counter++;
310
311        for (int u : adj[v]) {
312            if (ids[u] == -1) {
313                dfs(u, v);
314                low[v] = min(low[v], low[u]);
315
316                if (low[u] > ids[v]) {
317                    bridges.push_back({v, u});
318                }
319            } else if (u != parent) {
320                low[v] = min(low[v], ids[u]);
321            }
322        }
323    }
324
325public:
326    Bridges(int n, const vector<vector<int>>& adj) : n(n), adj(adj) {
327        ids.assign(n, -1);
328        low.assign(n, 0);
329        counter = 0;
330
331        for (int i = 0; i < n; i++) {
332            if (ids[i] == -1) {
333                dfs(i, -1);
334            }
335        }
336    }
337
338    vector<pair<int, int>> getBridges() { return bridges; }
339};
340
341// =============================================================================
342// ํ…Œ์ŠคํŠธ
343// =============================================================================
344
345#include <set>
346
347int main() {
348    cout << "============================================================" << endl;
349    cout << "๊ฐ•ํ•œ ์—ฐ๊ฒฐ ์š”์†Œ ์˜ˆ์ œ" << endl;
350    cout << "============================================================" << endl;
351
352    // ํ…Œ์ŠคํŠธ ๊ทธ๋ž˜ํ”„
353    //  0 โ†’ 1 โ†’ 2 โ†’ 3
354    //  โ†‘   โ†“       โ†“
355    //  4 โ† 5   6 โ† 7
356    //      โ†“
357    //      6
358
359    int n = 8;
360    vector<vector<int>> adj(n);
361    adj[0] = {1};
362    adj[1] = {2, 5};
363    adj[2] = {3};
364    adj[3] = {7};
365    adj[4] = {0};
366    adj[5] = {4, 6};
367    adj[6] = {};
368    adj[7] = {6};
369
370    // 1. Tarjan's Algorithm
371    cout << "\n[1] Tarjan's Algorithm" << endl;
372    TarjanSCC tarjan(n, adj);
373    cout << "    SCC ๊ฐœ์ˆ˜: " << tarjan.getSCCCount() << endl;
374    cout << "    SCCs:" << endl;
375    for (const auto& scc : tarjan.getSCCs()) {
376        cout << "      { ";
377        for (int v : scc) cout << v << " ";
378        cout << "}" << endl;
379    }
380
381    // 2. Kosaraju's Algorithm
382    cout << "\n[2] Kosaraju's Algorithm" << endl;
383    KosarajuSCC kosaraju(n, adj);
384    cout << "    SCC ๊ฐœ์ˆ˜: " << kosaraju.getSCCCount() << endl;
385
386    // 3. 2-SAT
387    cout << "\n[3] 2-SAT" << endl;
388    // (x0 โˆจ x1) โˆง (ยฌx0 โˆจ x2) โˆง (ยฌx1 โˆจ ยฌx2)
389    TwoSAT sat(3);
390    sat.addClause(0, 1);         // x0 โˆจ x1
391    sat.addClause(-1, 2);        // ยฌx0 โˆจ x2
392    sat.addClause(-2, -3);       // ยฌx1 โˆจ ยฌx2
393
394    if (sat.solve()) {
395        cout << "    ์ถฉ์กฑ ๊ฐ€๋Šฅ" << endl;
396        auto assignment = sat.getAssignment();
397        cout << "    ํ• ๋‹น: ";
398        for (int i = 0; i < 3; i++) {
399            cout << "x" << i << "=" << assignment[i] << " ";
400        }
401        cout << endl;
402    } else {
403        cout << "    ์ถฉ์กฑ ๋ถˆ๊ฐ€๋Šฅ" << endl;
404    }
405
406    // 4. ์ ˆ๋‹จ์ 
407    cout << "\n[4] ์ ˆ๋‹จ์  (๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„)" << endl;
408    vector<vector<int>> undirected(5);
409    undirected[0] = {1};
410    undirected[1] = {0, 2, 3};
411    undirected[2] = {1, 3};
412    undirected[3] = {1, 2, 4};
413    undirected[4] = {3};
414
415    ArticulationPoints ap(5, undirected);
416    auto points = ap.getArticulationPoints();
417    cout << "    ์ ˆ๋‹จ์ : ";
418    for (int v : points) cout << v << " ";
419    cout << endl;
420
421    // 5. ๋ธŒ๋ฆฟ์ง€
422    cout << "\n[5] ๋ธŒ๋ฆฟ์ง€ (๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„)" << endl;
423    Bridges br(5, undirected);
424    auto bridgeList = br.getBridges();
425    cout << "    ๋ธŒ๋ฆฟ์ง€: ";
426    for (auto [u, v] : bridgeList) {
427        cout << "(" << u << "-" << v << ") ";
428    }
429    cout << endl;
430
431    // 6. ๋ณต์žก๋„ ์š”์•ฝ
432    cout << "\n[6] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
433    cout << "    | ์•Œ๊ณ ๋ฆฌ์ฆ˜    | ์‹œ๊ฐ„๋ณต์žก๋„ | ์šฉ๋„               |" << endl;
434    cout << "    |-------------|------------|---------------------|" << endl;
435    cout << "    | Tarjan      | O(V + E)   | SCC, ๋‹จ์ผ DFS       |" << endl;
436    cout << "    | Kosaraju    | O(V + E)   | SCC, 2๋ฒˆ DFS        |" << endl;
437    cout << "    | 2-SAT       | O(V + E)   | ๋…ผ๋ฆฌ์‹ ์ถฉ์กฑ ๊ฐ€๋Šฅ์„ฑ  |" << endl;
438    cout << "    | ์ ˆ๋‹จ์       | O(V + E)   | ๊ทธ๋ž˜ํ”„ ์ทจ์•ฝ์        |" << endl;
439    cout << "    | ๋ธŒ๋ฆฟ์ง€      | O(V + E)   | ๊ทธ๋ž˜ํ”„ ์ทจ์•ฝ์        |" << endl;
440
441    cout << "\n============================================================" << endl;
442
443    return 0;
444}