出题人题解 | #国政议事#

原题解链接：https://ac.nowcoder.com/discuss/150007

暴力

#define _CRT_SECURE_NO_DEPRECATE
/************************
*创建时间：2018 09 14
*文件类型：源代码文件
*题目来源：原创题
*当前状态：已通过
*备忘录：最大匹配关键边 标程
*作者：HtBest
************************/
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <bitset>
// #include <sys/wait.h>
// #include <sys/types.h>
// #include <unistd.h>
using namespace std;
#define MAXN 501
#define MAXM 20001
int n,m,head[2*MAXN],_edge,to[MAXN],dfsx[2*MAXN],_dfsx,low[2*MAXN],toe[MAXN];
bitset <MAXN> visX,visY,marchX,keyX,keyY;
bitset <MAXM> marchE,bridge;
struct EDGE
{
	int a,b,next;
	EDGE(int a=0,int b=0,int next=0):a(a),b(b),next(next){}
}edge[MAXM],edge2[MAXM];
/* Variable explain:
n:人数
m:边数
head[i]:节点i的第一条出边
edge[i]:邻接表
_edge:邻接表标记
edge2[i]:重新建图缓存
to[i]:Y集合中i点的匹配点
toe[i]:Y集合中i点的匹配边
dfsx[i]:dfs序
_dfsx:dfs序标记
low[i]:每个点能访问到的最小dfs序的点
visX[i]:X集合中i点访问标记
visY[i]:Y集合中i点访问标记
visE[i]:二分图中边i的访问标记
marchX[i]:标记X集合中i是否为匹配点
marchE[i]:标记Y集合中i是否为匹配点
keyX[i]:标记X集合中i是否为关键点
keyY[i]:标记Y集合中i是否为关键点
*/
void adde(int a,int b)
{
	edge[++_edge]=EDGE(a,b,head[a]);
	head[a]=_edge;
}
void read()
{
	int ls1,ls2;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)scanf("%d%d",&ls1,&ls2),adde(ls1,ls2);
	return;
}
bool find(int a)
{
	visX[a]=true;
	for(int i=head[a];i;i=edge[i].next)
	{
		int b=edge[i].b;
		if(visY[b])continue;
		visY[b]=true;
		if(!to[b]||find(to[b]))
		{
			marchE[toe[b]]=false;
			marchE[i]=true;
			marchX[a]=true;
			to[b]=a;
			toe[b]=i;
			return true;
		}
	}
	return false;
}
bool find_only(int a)
{
	visX[a]=true;
	for(int i=head[a];i;i=edge[i].next)
	{
		int b=edge[i].b;
		if(visY[b])continue;
		visY[b]=true;
		if(!to[b]||find_only(to[b]))	return true;
	}
	return false;
}
void maxmarch()
{
	int ans=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)visY[j]=0;
		ans+=find(i);
	}
	for(int i=1;i<=n;++i)visX[i]=visY[i]=0;
	for(int i=1;i<=n;++i)if(!marchX[i])find_only(i);
	for(int i=1;i<=n;++i)keyX[i]=!visX[i];//求左侧关键点
	for(int i=1;i<=n;++i)//求右侧关键点
	{
		if(!to[i])continue;
		for(int j=1;j<=n;++j)visY[j]=0;
		if(!find_only(to[i]))keyY[i]=true;
	}
	printf("%d ",ans);
	// for(int i=1;i<=n;++i)if(keyX[i])printf("%d ",i);puts("");
	// for(int i=1;i<=n;++i)if(keyY[i])printf("%d ",i);puts("");
	// for(int i=1;i<=_edge;++i)if(marchE[i])printf("%d ",i);puts("");
}
void tarjan(int a,int start)
{
	dfsx[a]=low[a]=++_dfsx;
	for(int i=head[a];i;i=edge[i].next)
	{
		int b=edge[i].b;
		if(!dfsx[b])tarjan(b,start),low[a]=min(low[a],low[b]);
		else if(dfsx[b]>start)low[a]=min(low[a],dfsx[b]);
		if(low[b]>dfsx[a])bridge[i]=true;//没有返祖边
	}
}
int main()
{
	// freopen("pol_cov.in","r",stdin);
	// freopen("pol_cov.out","w",stdout);
	read();
	maxmarch();
	for(int i=1;i<=_edge;++i)edge2[i]=edge[i];
	int ls1=_edge;
	_edge=0;
	for(int i=1;i<=n;++i)head[i]=0;
	for(int i=1;i<=ls1;++i)
		if(marchE[i])adde(edge2[i].a,edge2[i].b+n);
		else adde(edge2[i].b+n,edge2[i].a);
	for(int i=1;i<=n;++i)if(!dfsx[i])tarjan(i,_dfsx);
	for(int i=1;i<=_edge;++i)
	{
		int &a=edge[i].a,&b=edge[i].b;
		if(a>n)a=0;
		else a=keyX[a];
		if(b>n)b=keyY[b-n];
		else b=keyX[b];
	}
	int cnt=0;
	for(int i=1;i<=_edge;++i)if(bridge[i]&&edge[i].a&&edge[i].b)++cnt;
	printf("%d\n",cnt);
	for(int i=1;i<=_edge;++i)if(bridge[i]&&edge[i].a&&edge[i].b)printf("%d\n",i);
	return 0;
}