17_scc.c - Examples

  1/*
  2 * 강한 연결 요소 (SCC - Strongly Connected Components)
  3 * Kosaraju, Tarjan Algorithm
  4 *
  5 * 방향 그래프에서 서로 도달 가능한 정점 집합을 찾습니다.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11#include <string.h>
 12
 13#define MAXN 1005
 14
 15/* =============================================================================
 16 * 1. 그래프 구조
 17 * ============================================================================= */
 18
 19typedef struct Node {
 20    int vertex;
 21    struct Node* next;
 22} Node;
 23
 24Node* graph[MAXN];
 25Node* reverse_graph[MAXN];
 26int n, m;
 27
 28void add_edge(Node** g, int u, int v) {
 29    Node* node = malloc(sizeof(Node));
 30    node->vertex = v;
 31    node->next = g[u];
 32    g[u] = node;
 33}
 34
 35/* =============================================================================
 36 * 2. Kosaraju 알고리즘
 37 * ============================================================================= */
 38
 39bool visited[MAXN];
 40int finish_stack[MAXN];
 41int stack_top;
 42int scc_id[MAXN];
 43int scc_count;
 44
 45void dfs1(int v) {
 46    visited[v] = true;
 47    Node* node = graph[v];
 48    while (node) {
 49        if (!visited[node->vertex])
 50            dfs1(node->vertex);
 51        node = node->next;
 52    }
 53    finish_stack[stack_top++] = v;
 54}
 55
 56void dfs2(int v, int scc_num) {
 57    visited[v] = true;
 58    scc_id[v] = scc_num;
 59    Node* node = reverse_graph[v];
 60    while (node) {
 61        if (!visited[node->vertex])
 62            dfs2(node->vertex, scc_num);
 63        node = node->next;
 64    }
 65}
 66
 67int kosaraju(void) {
 68    /* 1단계: 정방향 DFS */
 69    memset(visited, false, sizeof(visited));
 70    stack_top = 0;
 71    for (int i = 0; i < n; i++) {
 72        if (!visited[i])
 73            dfs1(i);
 74    }
 75
 76    /* 2단계: 역방향 DFS */
 77    memset(visited, false, sizeof(visited));
 78    scc_count = 0;
 79    for (int i = stack_top - 1; i >= 0; i--) {
 80        int v = finish_stack[i];
 81        if (!visited[v]) {
 82            dfs2(v, scc_count);
 83            scc_count++;
 84        }
 85    }
 86
 87    return scc_count;
 88}
 89
 90/* =============================================================================
 91 * 3. Tarjan 알고리즘
 92 * ============================================================================= */
 93
 94int disc[MAXN];
 95int low[MAXN];
 96bool on_stack[MAXN];
 97int tarjan_stack[MAXN];
 98int tarjan_top;
 99int timer;
100int tarjan_scc_count;
101int tarjan_scc_id[MAXN];
102
103void tarjan_dfs(int v) {
104    disc[v] = low[v] = timer++;
105    tarjan_stack[tarjan_top++] = v;
106    on_stack[v] = true;
107
108    Node* node = graph[v];
109    while (node) {
110        int u = node->vertex;
111        if (disc[u] == -1) {
112            tarjan_dfs(u);
113            if (low[u] < low[v]) low[v] = low[u];
114        } else if (on_stack[u]) {
115            if (disc[u] < low[v]) low[v] = disc[u];
116        }
117        node = node->next;
118    }
119
120    /* SCC 발견 */
121    if (low[v] == disc[v]) {
122        while (true) {
123            int u = tarjan_stack[--tarjan_top];
124            on_stack[u] = false;
125            tarjan_scc_id[u] = tarjan_scc_count;
126            if (u == v) break;
127        }
128        tarjan_scc_count++;
129    }
130}
131
132int tarjan(void) {
133    memset(disc, -1, sizeof(disc));
134    memset(low, -1, sizeof(low));
135    memset(on_stack, false, sizeof(on_stack));
136    timer = 0;
137    tarjan_top = 0;
138    tarjan_scc_count = 0;
139
140    for (int i = 0; i < n; i++) {
141        if (disc[i] == -1)
142            tarjan_dfs(i);
143    }
144
145    return tarjan_scc_count;
146}
147
148/* =============================================================================
149 * 4. SCC DAG 구성
150 * ============================================================================= */
151
152typedef struct {
153    int* edges;
154    int size;
155    int capacity;
156} EdgeSet;
157
158EdgeSet scc_graph[MAXN];
159
160void build_scc_dag(void) {
161    for (int i = 0; i < scc_count; i++) {
162        scc_graph[i].edges = malloc(n * sizeof(int));
163        scc_graph[i].size = 0;
164        scc_graph[i].capacity = n;
165    }
166
167    bool** added = malloc(scc_count * sizeof(bool*));
168    for (int i = 0; i < scc_count; i++) {
169        added[i] = calloc(scc_count, sizeof(bool));
170    }
171
172    for (int u = 0; u < n; u++) {
173        Node* node = graph[u];
174        while (node) {
175            int v = node->vertex;
176            int scc_u = scc_id[u];
177            int scc_v = scc_id[v];
178            if (scc_u != scc_v && !added[scc_u][scc_v]) {
179                scc_graph[scc_u].edges[scc_graph[scc_u].size++] = scc_v;
180                added[scc_u][scc_v] = true;
181            }
182            node = node->next;
183        }
184    }
185
186    for (int i = 0; i < scc_count; i++) free(added[i]);
187    free(added);
188}
189
190/* =============================================================================
191 * 테스트
192 * ============================================================================= */
193
194void cleanup(void) {
195    for (int i = 0; i < n; i++) {
196        Node* node = graph[i];
197        while (node) {
198            Node* temp = node;
199            node = node->next;
200            free(temp);
201        }
202        graph[i] = NULL;
203
204        node = reverse_graph[i];
205        while (node) {
206            Node* temp = node;
207            node = node->next;
208            free(temp);
209        }
210        reverse_graph[i] = NULL;
211    }
212}
213
214int main(void) {
215    printf("============================================================\n");
216    printf("강한 연결 요소 (SCC) 예제\n");
217    printf("============================================================\n");
218
219    /*
220     * 그래프:
221     *   0 → 1 → 2 → 0 (SCC: {0,1,2})
222     *   ↓       ↓
223     *   3 ← 4 ← 5 (SCC: {3,4,5})
224     */
225    n = 6;
226    add_edge(graph, 0, 1);
227    add_edge(graph, 1, 2);
228    add_edge(graph, 2, 0);
229    add_edge(graph, 0, 3);
230    add_edge(graph, 2, 5);
231    add_edge(graph, 5, 4);
232    add_edge(graph, 4, 3);
233    add_edge(graph, 3, 4);  /* 3,4,5 사이클 */
234
235    /* 역그래프 구성 */
236    add_edge(reverse_graph, 1, 0);
237    add_edge(reverse_graph, 2, 1);
238    add_edge(reverse_graph, 0, 2);
239    add_edge(reverse_graph, 3, 0);
240    add_edge(reverse_graph, 5, 2);
241    add_edge(reverse_graph, 4, 5);
242    add_edge(reverse_graph, 3, 4);
243    add_edge(reverse_graph, 4, 3);
244
245    /* 1. Kosaraju */
246    printf("\n[1] Kosaraju 알고리즘\n");
247    int num_scc = kosaraju();
248    printf("    SCC 개수: %d\n", num_scc);
249    printf("    노드별 SCC ID:\n    ");
250    for (int i = 0; i < n; i++)
251        printf("%d→SCC%d  ", i, scc_id[i]);
252    printf("\n");
253
254    /* 2. Tarjan */
255    printf("\n[2] Tarjan 알고리즘\n");
256    int num_scc2 = tarjan();
257    printf("    SCC 개수: %d\n", num_scc2);
258    printf("    노드별 SCC ID:\n    ");
259    for (int i = 0; i < n; i++)
260        printf("%d→SCC%d  ", i, tarjan_scc_id[i]);
261    printf("\n");
262
263    /* 3. SCC DAG */
264    printf("\n[3] SCC 축약 그래프 (DAG)\n");
265    build_scc_dag();
266    printf("    SCC 간 간선:\n");
267    for (int i = 0; i < scc_count; i++) {
268        printf("      SCC%d → ", i);
269        for (int j = 0; j < scc_graph[i].size; j++)
270            printf("SCC%d ", scc_graph[i].edges[j]);
271        printf("\n");
272        free(scc_graph[i].edges);
273    }
274
275    /* 4. 알고리즘 비교 */
276    printf("\n[4] 알고리즘 비교\n");
277    printf("    | 알고리즘  | 시간복잡도 | DFS 횟수 | 특징          |\n");
278    printf("    |-----------|------------|----------|---------------|\n");
279    printf("    | Kosaraju  | O(V + E)   | 2번      | 역그래프 필요 |\n");
280    printf("    | Tarjan    | O(V + E)   | 1번      | low-link 사용 |\n");
281
282    cleanup();
283
284    printf("\n============================================================\n");
285
286    return 0;
287}