题目链接

  本题是2003年icpc欧洲区域赛东北欧赛区的K题

题意

  从前有一个国王，他有n（n≤2000）个儿子。皇宫里还有n个美丽的女孩，并且国王知道每一个王子喜欢的女孩都是谁。王子们都年轻强壮并且富有智慧，所以一个王子喜欢很多女孩也是很正常的。
  国王找到巫师，告诉巫师每个王子所喜欢的女孩们，并且要求巫师找到一种方案，使每个王子都娶到一个自己喜欢的女孩。当然，一个女孩只能嫁给一个王子。
  巫师提交了一种方案，国王看了之后说：“我挺喜欢你的方案，但我不是十分满意。我还想知道每一个王子能娶的所有女孩，当然，他娶了某个女孩之后，剩下的其他王子还是可以找到自己喜欢的人作为自己的伴侣。”
  输入n个王子各自喜欢的女孩的列表，以及巫师提交的方案（即每个王子的新娘），你的任务是计算出每个王子有可能娶到的女孩的列表。

分析

  经典问题：已知二分图的一个最大匹配方案，怎么求其他匹配方案。不过作为婚姻问题，本题只有男方有候选列表，女方被动等待分配结果。
  可以借助有向图强连通分量的Tarjan算法求解（求出所有scc后，如果某男和某女在同一个scc且可以匹配——此女在某男的候选列表，则两者匹配后，其他男女间仍然存在最大匹配方案），说一下建图方法：利用男方候选列表加单向边$x_i\to y_j$，利用一个完美匹配的方案加单向边$y_i\to x_j$。思路参考自这篇博客。

AC 代码

#include <iostream>
#include <cstring>
using namespace std;#define N 4020
int g[N][N>>1], c[N], s[N], sn[N], pre[N], clk, cc, n, p = 0;int dfs(int u) {int low = pre[u] = ++clk; s[p++] = u;for (int i=0, v; i<c[u]; ++i) if (!pre[v = g[u][i]]) {low = min(low, dfs(v));} else if (!sn[v]) low = min(low, pre[v]);if (low == pre[u]) {++cc;while (true) {sn[s[--p]] = cc;if (s[p] == u) break;}}return low;
}void solve () {memset(pre, clk = 0, sizeof(pre)); memset(sn, cc = p = 0, sizeof(sn));for (int i=1; i<=n; ++i) {cin >> c[i]; c[i+n] = 1;for (int j=0; j<c[i]; ++j) cin >> g[i][j], g[i][j] += n;}for (int i=1, x; i<=n; ++i) cin >> x, g[x+n][0] = i;for (int u=1; u<=n; ++u) if (!pre[u]) dfs(u);for (int i=1, k; i<=n; ++i) {for (int j=k=0, x; j<c[i]; ++j) if (sn[i] == sn[x = g[i][j]]) s[k++] = x-n;cout << k;while (k--) cout << ' ' << s[k];cout << endl;}
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n) solve();return 0;
}