P1793 跑步

题目描述

新牛到部队，CG 要求它们每天早上搞晨跑，从 $A$ 农场跑到 $B$ 农场。从 $A$ 农场到 $B$ 农场中有 $n-2$ 个路口，分别标上号，$A$ 农场为 $1$ 号，$B$ 农场为 $n$ 号，路口分别为 $2,3,4,\cdots ,n-1$ 号，从 $A$ 农场到 $B$ 农场有很多条路径可以到达，而 CG 发现有的路口是必须经过的，即每条路径都经过的路口，CG 要把它们记录下来，这样 CG 就可以先到那个路口，观察新牛们有没有偷懒，而你的任务就是找出所有必经路口。

输入格式

第一行两个用空格隔开的整数 $n(3\le n\le 2000)$ 和 $e(1\le e\le 8000)$。

接下来从第 $2$ 到第 $e+1$ 行，每行两个用空格隔开的整数 $p$ 和 $q$，表示路口 $p$ 和 $q$ 之间有路径直达。

输入数据保证必经路口一定存在，并且每个路口都和 $A$ 农场、$B$ 农场相连通。

输出格式

第一行一个整数 $m$，表示必经路口的数目。

第二行按从小到大的顺序依次输出每个必经路口的编号，每两个数之间用一个空格隔开。

输入输出样例 #1

输入 #1

6 6
1 2
2 4
2 3
3 5
4 5
5 6

输出 #1

2
2 5

C++实现

#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]<<" ";//输出 
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容