自动搬运

查看原文

来自洛谷，原作者为

	游戏的人 这个家伙太弱，什么也没有留下

搬运于2025-08-24 21:30:24，当前版本为作者最后更新于2020-04-03 10:27:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

难道就没人想到暴力吗

刚开始以为是割点题，发现其实从起点到终点的必经之路就算没了，图也可能还是联通的，所以便可以想到暴力。

思路

可以用邻接链表把图存起来，再枚举2到N-1的点为必经之路，再沿着路径搜索，判断没有这个点能不能到达终点，能的话就说明这个点不是必经之路，直接退出。如果不能到终点就说明必须要走这个点，就存到答案里。

每次经过这个点都要打上标记。本题不需要回溯，只需要判断这个点有没有走过，因为只需要判断搜到这个点有没有路径，不用判断是怎么走的，所以只需要判断有没有重复搜点就行了。每次枚举时记得标记数组清零。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,f[8001],k,num,sum=0,ans[8001],s[8001];
bool flag;
struct edge 
{
	int f,t;
}a[4000001];//定义边长 
void add(int x1,int y1)
{
	a[++num].f=s[x1];
	a[num].t=y1;
	s[x1]=num;
}//邻接链表存图 
void dfs(int x,int k)
{
	if(x==n){flag=1;return;}//判断如果能到终点就标记不是必经之路 
	if(f[x]==1||x==k||flag==1)return;//如果这个点搜过，或者到了切断的必经之路，或者已到达终点就返回 
	f[x]=1;//走过标记 
	for(int i=s[x];i;i=a[i].f)dfs(a[i].t,k);//邻接链表搜索 
} 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int xi,yi;
		cin>>xi>>yi;
		if(xi==yi)continue;//判断自环 
	    add(xi,yi);add(yi,xi);//无向图正反存 
	}
	for(int i=2;i<=n-1;i++)
	{
		for(int j=1;j<=n;j++)f[j]=0;//开始标记数组清零 
		flag=0;//终点标记初始化 
		dfs(1,i);//起点1,枚举的必经之路是i 
		if(flag==0)sum++,ans[sum]=i;//答案+1，存入数组，两者并列 
	}
	cout<<sum<<endl; 
	for(int i=1;i<=sum;i++)cout<<ans[i]<<" ";//输出 
}

完结撒花

留个赞吧