简单解题思路

问题描述

给定 n 个王子和 n 个公主的配对关系（双向选择），要求：

1. 找出每个王子可以配对的公主集合，这些公主必须满足：
   • 该公主也选择了该王子（双向选择）；
   • 属于同一个强连通分量（表示可以互相到达）。

核心思想

1. 图建模：

   • 将王子和公主分别编号为 1~n 和 n+1~2n。
   • 建立有向边表示选择关系：
     • 王子 i → 公主 j（i 选择了 j）；
     • 公主 j → 王子 i（j 也选择了 i）。

2. 强连通分量（SCC）分解：

   • 使用 Tarjan 算法 找出所有强连通分量（SCC）。
   • 同一个 SCC 内的王子和公主可以互相配对（因为双向可达）。

3. 结果统计：

   • 对于每个王子 i，遍历其选择的公主 j，若 j 和 i 属于同一个 SCC，则 j 是有效配对。
   • 输出每个王子能配对的公主列表（排除无效选择）。

关键步骤

1. 输入处理：

   • 读取每个王子选择的公主列表，建立王子→公主的边；
   • 读取每个公主选择的王子，建立公主→王子的边。

2. Tarjan 算法：

   • 计算所有 SCC，并标记每个节点所属的 SCC 编号 belong[u]。
   • 在 SCC 处理过程中，记录每个王子能配对的公主（同一 SCC 内）。

3. 输出结果：

   • 对每个王子的候选公主列表排序，去除非同一 SCC 的公主；
   • 输出每个王子的有效配对公主编号（减去 n 还原为原始编号）。

总结

• 核心算法：Tarjan 强连通分量算法。
• 适用场景：双向选择匹配问题（如稳定婚姻问题的变种）。
• 优化点：利用 SCC 性质快速筛选有效配对，避免暴力枚举。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=4e3+5;
const int INF=1e9+7;
const ll mod=998244353;
int n,m,tot,cnt,dfn[maxn],low[maxn],belong[maxn];
vector<int> v[maxn],ans[maxn],res;
bool vis[maxn];
stack<int> s;
void tarjan(int u)
{
	dfn[u]=low[u]=++tot;
	vis[u]=1,s.push(u);
	for(int i=0;i<v[u].size();i++)
	{
		int g=v[u][i];
		if(!dfn[g])
		{
			tarjan(g);
			low[u]=min(low[u],low[g]);
		}
		else if(vis[g]) low[u]=min(low[u],dfn[g]);
	}
	if(dfn[u]==low[u])
	{
		cnt++;
		res.clear();
		while(!s.empty())
		{
			int now=s.top();
			s.pop();vis[now]=0;
			res.push_back(now);
			belong[now]=cnt;
			if(now==u) break;
		}
		for(int i=0;i<res.size();i++)   //处理出每个王子的公主
		{
			if(res[i]<=n)
			{
				for(int j=0;j<v[res[i]].size();j++)
				{
					if(belong[v[res[i]][j]]==cnt&&v[res[i]][j]>n)
						ans[res[i]].push_back(v[res[i]][j]);
				}
			}
		}
	}
}
void print()    //输出每个王子所对应的公主
{
	for(int i=1;i<=n;i++)
	{
		int res=0;
		sort(ans[i].begin(),ans[i].end());
		for(int j=0;j<ans[i].size();j++) if(ans[i][j]<=n) res++;
		printf("%d",ans[i].size()-res);
		for(int j=0;j<ans[i].size();j++)
			if(ans[i][j]>n) printf(" %d",ans[i][j]-n);
		printf("\n");
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int m,x;
		scanf("%d",&m);
		for(int j=0;j<m;j++)    //这里注意x+n
		{
			scanf("%d",&x);
			v[i].push_back(x+n);
		}
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		v[x+n].push_back(i);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i);
	print();
	//system("pause");
}