题目描述
图一表示一次街道赛跑的跑道。可以看出有一些路口（用 \(0\) 到 \(N\) 的整数标号），和连接这些路口的箭头。路口 \(0\) 是跑道的起点，路口 \(N\) 是跑道的终点。箭头表示单行道。运动员们可以顺着街道从一个路口移动到另一个路口（只能按照箭头所指的方向）。当运动员处于路口位置时，他可以选择任意一条由这个路口引出的街道。
图一：有 \(10\) 个路口的街道
一个良好的跑道具有如下几个特点：
- 每一个路口都可以由起点到达。
- 从任意一个路口都可以到达终点。
- 终点不通往任何路口。
运动员不必经过所有的路口来完成比赛。有些路口却是选择任意一条路线都必须到达的（称为“不可避免”的）。在上面的例子中，这些路口是 \(0\)，\(3\)，\(6\)，\(9\)。对于给出的良好的跑道，你的程序要确定“不可避免”的路口的集合，不包括起点和终点。
假设比赛要分两天进行。为了达到这个目的，原来的跑道必须分为两个跑道，每天使用一个跑道。第一天，起点为路口 \(0\)，终点为一个“中间路口”；第二天，起点是那个中间路口，而终点为路口 \(N\)。对于给出的良好的跑道，你的程序要确定“中间路口”的集合。如果良好的跑道 \(C\) 可以被路口 \(S\) 分成两部分，这两部分都是良好的，并且 \(S\) 不同于起点也不同于终点，同时被分割的两个部分满足下列条件：（1）它们之间没有共同的街道（2）\(S\) 为它们唯一的公共点，并且 \(S\) 作为其中一个的终点和另外一个的起点。那么我们称 \(S\) 为“中间路口 ”。在例子中只有路口 \(3\) 是中间路口。
输入格式
输入文件包括一个良好的跑道，最多有 \(50\) 个路口，\(100\) 条单行道。
共有 \(N+2\) 行，前面 \(N+1\) 行中第 \(i\) 行表示以编号为 \(i-1\) 的路口作为起点的街道，每个数字表示一个终点。行末用 -2 作为结束。最后一行只有一个数字 -1。
输出格式
第一行：跑道中“不可避免的路口”的数量，接着是这些路口的序号，序号按照升序排列。
第二行：跑道中“中间路口”的数量，接着是这些路口的序号，序号按照升序排列。
样例输入
1 2 -2
3 -2
3 -2
5 4 -2
6 4 -2
6 -2
7 8 -2
9 -2
5 9 -2
-2
-1
样例输出
2 3 6
13
首先我们可以枚举每一个点，看看删掉后能不能从起点走到终点，如果不可以，说明这个点是“不可避免的路口”
显而易见，如果一个点不是“不可避免的路口”，那么它不可能是“中间路口”
而一个点如果是“不可避免的路口”，那么就可以尝试从起点走到这个点，以及从这个点走到终点，如果路径有重合，则说明不是“中间路口”
这道题主要难在对细节的处理，可以给大家列举几个：
- 清空
vis数组 - 中间路口并不算重合
- 题目说了不用枚举起点与终点
- 刚开始要把自己标记上（防止出现环）
#include<bits/stdc++.h>
using namespace std;
int n,cnt,tot;
const int N=55;
int g[N][N],vis1[N],vis2[N],bk[N],zj[N];
void dfs1(int x){
vis1[x]=1;
for(int i=0;i<=n;i++){
if(!vis1[i]&&g[x][i]){
dfs1(i);
}
}
}
void dfs2(int x){
vis2[x]=1;
for(int i=0;i<=n;i++){
if(!vis2[i]&&g[x][i]){
dfs2(i);
}
}
}
int main()
{
while(true){
int x;
scanf("%d",&x);
if(x==-1) break;
if(x==-2) n++;
else g[n][x]=1;
}
n--;
for(int i=1;i<=n-1;i++){//第三个细节
memset(vis1,0,sizeof(vis1));//第一个细节
vis1[i]=1;//第四个细节
dfs1(0);
if(!vis1[n]){
bk[++cnt]=i;
memset(vis2,0,sizeof(vis2));
vis2[i]=1;
dfs2(i);
int check=1;
for(int j=0;j<=n;j++){
if(vis1[j]&&vis2[j]&&j!=i){//j!=i处理第二个细节
check=0;
break;
}
}
if(check) zj[++tot]=i;
}
}
printf("%d ",cnt);
for(int i=1;i<=cnt;i++) printf("%d ",bk[i]);
printf("\n%d ",tot);
for(int i=1;i<=tot;i++) printf("%d ",zj[i]);
}