建图: 王子 u 喜欢女孩 v, 则 u 到 v 连一条边. 对于给出的初始完美匹配, 王子 u 与女孩 v 匹配, 则 v 到 u 连一条边. 然后求 SCC.
显然对于同一个 SCC 中王子数目和女孩数目是相等的, 并且从某个王子出发能够到达所有女孩, 这样, 王子可以和属于同一个 SCC 中的任意一个女孩结婚, 而不会影响其他王子.
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <vector>
- #define mem(a, b) memset(a, b, sizeof(a))
- using namespace std;
- const int maxn = 500100, INF = 0x7fffffff;
- int pre[maxn], low[maxn], sccno[maxn], dfs_clock, scc_cnt, cnt;
- int head[maxn];
- vector<int> G[maxn];
- stack<int> S;
- int n, k;
- struct node
- {
- int u, v, next;
- }Node[maxn];
- void add(int u, int v)
- {
- Node[cnt].u = u;
- Node[cnt].v = v;
- Node[cnt].next = head[u];
- head[u] = cnt++;
- }
- void dfs(int u)
- {
- pre[u] = low[u] = ++dfs_clock;
- S.push(u);
- for(int i=head[u]; i!=-1; i=Node[i].next)
- {
- int v = Node[i].v;
- if(!pre[v])
- {
- dfs(v);
- low[u] = min(low[u], low[v]);
- }
- else if(!sccno[v])
- low[u] = min(low[u], pre[v]);
- }
- if(low[u] == pre[u])
- {
- scc_cnt++;
- for(;;)
- {
- int x = S.top(); S.pop();
- sccno[x] = scc_cnt;
- if(x == u) break;
- }
- }
- }
- void init()
- {
- cnt = 0;
- mem(head, -1);
- mem(pre, 0);
- mem(low, 0);
- mem(sccno, 0);
- }
- int main()
- {
- init();
- scanf("%d",&n);
- for(int i=1; i<=n; i++)
- {
- scanf("%d",&k);
- for(int j=0; j<k; j++)
- {
- int v;
- scanf("%d",&v);
- add(i, n+v);
- }
- }
- for(int i=1; i<=n; i++)
- {
- int v;
- scanf("%d",&v);
- add(n+v, i);
- }
- for(int i=1; i<=n; i++)
- if(!pre[i])
- dfs(i);
- // cout<< 1211 <<endl;
- for(int i=1; i<=n; i++)
- {
- for(int j=head[i]; j!=-1; j=Node[j].next)
- {
- if(sccno[i] == sccno[Node[j].v])
- {
- G[i].push_back(Node[j].v);
- }
- }
- }
- for(int i=1; i<=n; i++)
- sort(G[i].begin(), G[i].end());
- for(int i=1; i<=n; i++)
- {
- printf("%d",G[i].size());
- for(int j=0; j<G[i].size(); j++)
- printf("%d%s",G[i][j] - n,(j==G[i].size()-1)?"\n":" ");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2684547.html