aboutsummaryrefslogtreecommitdiff
path: root/dom.c
diff options
context:
space:
mode:
Diffstat (limited to 'dom.c')
-rw-r--r--dom.c155
1 files changed, 155 insertions, 0 deletions
diff --git a/dom.c b/dom.c
new file mode 100644
index 0000000..7fbd948
--- /dev/null
+++ b/dom.c
@@ -0,0 +1,155 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#define MAXN 1000
+#define MAX_HASH 1021
+typedef struct Edge Edge;
+typedef struct Set Set;
+typedef Set *Set_t;
+typedef struct SetNode {
+ int val;
+ struct SetNode *next;
+} SetNode;
+struct Set {
+ SetNode *head[MAX_HASH];
+};
+
+Set_t set_create() {
+ Set_t set = (Set_t)malloc(sizeof(Set));
+ memset(set->head, 0, sizeof set->head);
+ return set;
+}
+
+int set_belongs(Set_t set, int val) {
+ SetNode *p;
+ for (p = set->head[val % MAX_HASH]; p; p = p->next)
+ if (p->val == val) return 1;
+ return 0;
+}
+
+void set_push(Set_t set, int val) {
+ SetNode *p = (SetNode*)malloc(sizeof(SetNode));
+ int hv = val % MAX_HASH;
+ p->next = set->head[hv];
+ p->val = val;
+ set->head[hv] = p;
+}
+
+struct Edge {
+ int to;
+ Edge *next;
+} *head[MAXN], *rhead[MAXN];
+
+typedef struct DFNode DFNode;
+struct DFNode {
+ int id;
+ DFNode *next;
+};
+
+void add_edge(int a, int b, Edge **head) {
+ Edge *p = (Edge*)malloc(sizeof(Edge));
+ p->to = b;
+ p->next = head[a];
+ head[a] = p;
+}
+int dom[MAXN], ord[MAXN], vis[MAXN], par[MAXN];
+int n, n0, m;
+DFNode *df[MAXN];
+Set_t dfset[MAXN];
+
+void dfs(int u, int v) {
+ static int ocnt = 0;
+ Edge *e;
+ if (vis[u] != -1) return;
+ par[u] = v;
+ vis[u] = 0;
+ for (e = head[u]; e; e = e->next)
+ dfs(e->to, u);
+ vis[u] = ocnt;
+ ord[ocnt++] = u;
+}
+
+int intersect(int b1, int b2) {
+ while (b1 != b2)
+ if (b1 < b2) b1 = dom[b1];
+ else b2 = dom[b2];
+ return b1;
+}
+
+int main() {
+ int i;
+ int ch = 1;
+ scanf("%d %d %d", &n, &m, &n0);
+ for (i = 0; i < m; i++)
+ {
+ int a, b;
+ scanf("%d %d", &a, &b);
+ add_edge(a, b, head);
+ add_edge(b, a, rhead);
+ }
+ for (i = 0; i < n; i++)
+ vis[i] = dom[i] = -1;
+ dfs(n0, -1);
+ for (i = 0; i < n; i++)
+ printf("%d ", ord[i]); puts("");
+ dom[vis[n0]] = vis[n0];
+ while (ch)
+ {
+ int i;
+ ch = 0;
+ for (i = n - 2; i >= 0; i--)
+ {
+ int id = ord[i];
+ Edge *e = rhead[id];
+ int new_idom = vis[par[id]];
+ for (; e; e = e->next)
+ {
+ int p = e->to;
+ if (p == new_idom) continue;
+ if (dom[vis[p]] != -1)
+ new_idom = intersect(vis[p], new_idom);
+ }
+ if (dom[i] != new_idom)
+ {
+ ch = 1;
+ dom[i] = new_idom;
+ }
+ }
+ for (i = 0; i < n; i++)
+ printf("%d ", ord[dom[vis[i]]]); puts("");
+ }
+ for (i = 0; i < n; i++)
+ {
+ dfset[i] = set_create();
+ df[i] = NULL;
+ }
+ for (i = 0; i < n; i++)
+ if (rhead[i] && rhead[i]->next)
+ {
+ Edge *p = rhead[i];
+ for (; p; p = p->next)
+ {
+ int runner = p->to;
+ while (vis[runner] != dom[vis[i]])
+ {
+ if (!set_belongs(dfset[runner], i))
+ {
+ DFNode *np = (DFNode*)malloc(sizeof(DFNode));
+ np->id = i;
+ np->next = df[runner];
+ set_push(dfset[runner], i);
+ df[runner] = np;
+ }
+ runner = ord[dom[vis[runner]]];
+ }
+ }
+ }
+ for (i = 0; i < n; i++)
+ {
+ DFNode *p = df[i];
+ printf("%d: ", i);
+ for (; p; p = p->next)
+ printf("%d ", p->id); puts("");
+ }
+ return 0;
+}