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
| #include <bits/stdc++.h>
#define R register #define ll long long #define cmax(a, b) ((a < b) ? b : a) #define cmin(a, b) ((a < b) ? a : b) #define sum(a, b, mod) ((a + b) % mod)
const int MaxN = 2e4 + 10; const int MaxM = 5e5 + 10; const int inf = (1 << 30);
struct edge { int to, next, cap; };
edge e[MaxM]; int n, m, s = 20000, t = 20001, cnt = 1, ans; int head[MaxN], dep[MaxN], cur[MaxN], a[MaxN], vis[MaxN], to[MaxN];
inline void add(int u, int v, int c) { ++cnt; e[cnt].to = v; e[cnt].next = head[u]; e[cnt].cap = c; head[u] = cnt; }
inline void add_edge(int u, int v, int c) { add(u, v, c), add(v, u, 0); }
inline int read() { int x = 0; char ch = getchar(); while (ch > '9' || ch < '0') ch = getchar(); while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return x; }
inline int bfs() { memset(dep, 0, sizeof(dep)); memcpy(cur, head, sizeof(head)); std::queue<int> q; dep[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i; i = e[i].next) { int v = e[i].to, c = e[i].cap; if (dep[v] || !c) continue; dep[v] = dep[u] + 1; q.push(v); } } return dep[t]; }
inline int dinic(int u, int flow) { if (u == t) return flow; int rest = flow; for (int i = cur[u]; i && (flow - rest < flow); i = e[i].next) { int v = e[i].to, c = e[i].cap; if (dep[v] != dep[u] + 1 || !c) continue; int k = dinic(v, cmin(rest, c)); if (!k) dep[v] = dep[u] + 1; else { e[i].cap -= k; e[i ^ 1].cap += k; rest -= k; if (e[i].to > n) vis[e[i].to - n] = 1; to[u] = e[i].to; } } if (flow - rest < flow) dep[u] = -1; return flow - rest; }
inline void solve() { int now = 0; while (bfs()) while ((now = dinic(s, inf))) ans += now; }
int main() { n = read(), m = read(); for (int i = 1; i <= m; i++) { int u = read(), v = read(); add_edge(u, v + n, inf); } for (int i = 1; i <= n; i++) add_edge(s, i, 1), add_edge(i + n, t, 1); solve(); for (int i = 1; i <= n; i++) { if (vis[i]) continue; printf("%d ", i); int t = i; while (to[t]) { printf("%d ", to[t] - n); t = to[t] - n; } puts(""); } printf("%d\n", n - ans); return 0; }
|