#include #define CBM_n_MAX 500000 #define CBM_m_MAX 1000000 typedef struct Edge { struct Edge *next; int v; } edge; int augment_cardinality_bipartite_matching_HK(int n, char color[], edge *adj[], int mate[]) { int u, w, m, head, tail; static int depth[CBM_n_MAX + 1], indeg[CBM_n_MAX + 1], q[CBM_n_MAX + 1]; static edge *aux[CBM_n_MAX + 1], *pred[CBM_n_MAX + 1], e[CBM_m_MAX * 2], *p; for (u = 1, tail = 0; u <= n; u++) { aux[u] = NULL; pred[u] = NULL; indeg[u] = 0; if (color[u] == 0 && mate[u] == 0) { depth[u] = 0; indeg[u] = 1; q[tail++] = u; } else depth[u] = -1; } for (head = 0, m = 0; head < tail; head++) { u = q[head]; if (color[u] == 0) { for (p = adj[u]; p != NULL; p = p->next) { w = p->v; if (w == mate[u]) continue; if (depth[w] < 0) { depth[w] = depth[u] + 1; q[tail++] = w; } if (depth[w] == depth[u] + 1) { e[m].v = w; e[m].next = aux[u]; aux[u] = &(e[m++]); e[m].v = u; e[m].next = pred[w]; pred[w] = &(e[m++]); indeg[w]++; } } } else if (mate[u] != 0) { w = mate[u]; if (depth[w] < 0) { depth[w] = depth[u] + 1; q[tail++] = w; } if (depth[w] == depth[u] + 1) { e[m].v = w; e[m].next = aux[u]; aux[u] = &(e[m++]); e[m].v = u; e[m].next = pred[w]; pred[w] = &(e[m++]); indeg[w]++; } } } int t, add = 0; for (t = 1; t <= n; t++) { if (color[t] == 0 || mate[t] != 0 || indeg[t] == 0) continue; else add++; for (u = t, tail = 0; 1; ) { indeg[u] = 0; q[tail++] = u; for (p = pred[u]; p != NULL; p = p->next) if (indeg[p->v] > 0) break; if (p == NULL) break; else u = p->v; } for (head = 0; head < tail; head += 2) { u = q[head]; w = q[head+1]; mate[u] = w; mate[w] = u; } for (head = 0; head < tail; head++) { u = q[head]; for (p = aux[u]; p != NULL; p = p->next) { w = p->v; indeg[w]--; if (indeg[w] == 0) q[tail++] = w; } } } return add; } int cardinality_bipartite_matching_HK(int n, char color[], edge *adj[], int mate[]) { int ans = 0, add, u; for (u = 1; u <= n; u++) mate[u] = 0; do { add = augment_cardinality_bipartite_matching_HK(n, color, adj, mate); ans += add; } while (add != 0); return ans; } int main() { int i, N, u, w, A[200001], B[200001]; edge *adj[400001] = {}, e[800001], *p; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d %d", &u, &w); e[i*4].v = N + i + 1; e[i*4].next = adj[u]; adj[u] = &(e[i*4]); e[i*4+1].v = u; e[i*4+1].next = adj[N+i+1]; adj[N+i+1] = &(e[i*4+1]); e[i*4+2].v = N + i + 1; e[i*4+2].next = adj[w]; adj[w] = &(e[i*4+2]); e[i*4+3].v = w; e[i*4+3].next = adj[N+i+1]; adj[N+i+1] = &(e[i*4+3]); A[i] = u; B[i] = w; } char color[400001]; int mate[400001]; for (u = 1; u <= N; u++) color[u] = 0; for (u = N + 1; u <= N * 2; u++) color[u] = 1; cardinality_bipartite_matching_HK(N * 2, color, adj, mate); for (i = 0; i < N; i++) { if (mate[N+i+1] == A[i]) printf("->\n"); else printf("<-\n"); } fflush(stdout); return 0; }