二分图最小点覆盖

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define endl '\n'
const int N = 5005, M = 555;

struct node
{
	int y, id;
};

vector<node> nbr[2 * N];

map<string, int> Mapst;
map<string, int> Maped;

int n, k, mth[2 * N], dfn[2 * N], cntst, cnted, tim, ans, as, Tsn[2 * N];

bool vis[2 * N];

string s[N];

void dfs(int cur, bool flag)
{
	vis[cur] = true;
	for(auto E : nbr[cur])
	{
		int nxt = E.y;
		if(vis[nxt])
			continue;
		dfs(nxt, !flag);
		if(flag)
			Tsn[++as] = nxt;
	}
	return ;
}
bool hungary(int cur, int ti)
{
	for(auto E : nbr[cur])
	{
		int nxt = E.y;
		if(dfn[nxt] >= ti)
			continue;
		dfn[nxt] = ti;
		if(!mth[nxt] || hungary(mth[nxt], ti))
		{
			mth[nxt] = cur;
			return true;
		}
	}
	return false;
}

signed main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i];
		string st = s[i].substr(0, k), ed = s[i].substr(s[i].size() - k);
		if(!Mapst[st])
			Mapst[st] = ++cntst;
	}
	cnted = cntst;
	for(int i = 1; i <= n; i++)
	{
		string st = s[i].substr(0, k), ed = s[i].substr(s[i].size() - k);
		if(!Maped[ed])
			Maped[ed] = ++cnted;
		nbr[Mapst[st]].push_back((node){Maped[ed], i});
		nbr[Maped[ed]].push_back((node){Maped[st], i});
	}
	for(int i = 1; i <= cntst; i++)
		if(hungary(i, ++tim))
			ans++;
	for(int i = cntst + 1; i <= cnted; i++)
		if(!mth[i])
			dfs(i, 1);
	for(int i = cntst + 1; i <= cnted; i++)
		if(mth[i] && !vis[i])
			Tsn[++as] = i;
	cout << as << endl;
	for(int i = 1; i <= as; i++)
	{
		cout << nbr[Tsn[i]].size() << ' ';
		for(auto E : nbr[Tsn[i]])
			cout << E.id << ' ';
		cout << endl;
	}
	return 0;
}