图一表示一次街道赛跑的跑道。可以看出有一些路口（用 0 到 N 的整数标号），和连接这些路口的箭头。路口 0 是跑道的起点，路口 N 是跑道的终点。箭头表示单行道。运动员们可以顺着街道从一个路口移动到另一个路口（只能按照箭头所指的方向）。当运动员处于路口位置时，他可以选择任意一条由这个路口引出的街道。
图一：有 10 个路口的街道 一个良好的跑道具有如下几个特点：
* 每一个路口都可以由起点到达。
* 从任意一个路口都可以到达终点。
* 终点不通往任何路口。
* 运动员不必经过所有的路口来完成比赛。有些路口却是选择任意一条路线都必须到达的（称为“不可避免”的）。在上面的例子中，这些路口是 0，3，6，9。对于给出的良好的跑道，你的程序要确定“不可避免”的路口的集合，不包括起点和终点。
假设比赛要分两天进行。为了达到这个目的，原来的跑道必须分为两个跑道，每天使用一个跑道。第一天，起点为路口 0，终点为一个“中间路口”；第二天，起点是那个中间路口，而终点为路口 N。对于给出的良好的跑道，你的程序要确定“中间路口”的集合。如果良好的跑道 C 可以被路口 S 分成两部分，这两部分都是良好的，并且 S 不同于起点也不同于终点，同时被分割的两个部分满足下列条件：（1）它们之间没有共同的街道（2）S 为它们唯一的公共点，并且 S 作为其中一个的终点和另外一个的起点。那么我们称 S 为“中间路口 ”。在例子中只有路口 3 是中间路口。
格式
PROGRAM NAME: race3
INPUT FORMAT:(file race3.in)
输入文件包括一个良好的跑道，最多有 50 个路口，100 条单行道。
一共有 N+2 行，前面 N+1 行中第 i 行表示以编号为(i-1)的路口作为起点的街道，每个数字表示一个终点。行末用 -2 作为结束。最后一行只有一个数字 -1。
OUTPUT FORMAT:(file race3.out)
你的程序要有两行输出：
第一行包括：跑道中“不可避免的”路口的数量，接着是这些路口的序号，序号按照升序排列。
第二行包括：跑道中“中间路口”的数量，接着是这些路口的序号，序号按照升序排列。
SAMPLE INPUT
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
SAMPLE OUTPUT
2 3 6
1 3
分析(nocow)：
1.一道基础的连通分量的图论题。这个题默认了0为起点，N为终点。(如果不放心可以再读入的时候判断起点和终点，即入度为0的点为起点，出度为0的点为终点。)
2.该题有两问，第一问很简单，可以尝试去掉每一个点，判断从起点到终点是否有通路，如果没有则该点为“必经点”。
3.第二问重点在于理解题意。首先可以确定第二问的解集是第一问的子集，所以我们可以第一问得出的每个点深搜，记录下可以到达的点。然后去掉该点，从起点深搜。如果不存在两次深搜皆可到达的点，就说明它是分割点。
【参考程序】：
/*
ID: XIONGNA1
PROG: race3
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
int map[101][101],must[101],mid[101];
short vis[101];
bool bk;
int n;
void cout_ans()
{
printf("%d",must[0]);
for (int i=1;i<=must[0];i++) printf(" %d",must[i]);
printf("\n%d",mid[0]);
for (int i=1;i<=mid[0];i++) printf(" %d",mid[i]);
printf("\n");
}
void dfs2(int s)
{
if (bk || vis[s]==2) return ;
vis[s]=2;
for (int i=1;i<=map[s][0];i++)
{
if (vis[map[s][i]]==1)
{
bk=true; return ;
}
dfs2(map[s][i]);
}
}
bool dfs1(int s)
{
if (s==n) return true;
for (int i=1;i<=map[s][0];i++)
if (vis[map[s][i]]==0)
{
vis[map[s][i]]=1;
if (dfs1(map[s][i])) return true;
}
return false;
}
void work()
{
must[0]=mid[0]=0;
for (int i=1;i<=n-1;i++)
{
memset(vis,0,sizeof(vis));
vis[0]=vis[i]=1;
if (!dfs1(0))
{
must[0]++; must[must[0]]=i;
bk=false;
dfs2(i);
if (!bk)
{
mid[0]++; mid[mid[0]]=i;
}
}
}
}
int main()
{
freopen("race3.in","r",stdin);
freopen("race3.out","w",stdout);
n=-1; int x;
memset(map,0,sizeof(map));
while (true)
{
n++;
while (scanf("%d",&x),x!=-1 && x!=-2)
{
map[n][0]++; map[n][map[n][0]]=x;
}
if (x==-1){ n--; break;}
}
work();
cout_ans();
return 0;
}
【参考程序】：
{
ID: XIONGNA1
PROG: race3
LANG: PASCAL
}
const maxn=101;
var contact:array[0..maxn,0..maxn] of integer;
visit:array[0..maxn] of shortint;
must,middle:array[0..maxn] of integer;
n,x:integer;
repeated:boolean;
procedure cout_ans;
var i:longint;
begin
write(must[0]);
for i:=1 to must[0] do write(' ',must[i]);
writeln;
write(middle[0]);
for i:=1 to middle[0] do write(' ',middle[i]);
writeln;
end;
procedure init;
begin
n:=-1;
while true do
begin
inc(n);
while not eoln do
begin
read(x);
if ((x=-2)or(x=-1)) then
begin
readln; break;
end;
inc(contact[n,0]);
contact[n,contact[n,0]]:=x;
end;
if (x=-1) then
begin
dec(n); break;
end;
end;
end;
function dfs1(v0:integer):boolean;
var i:integer;
begin
if v0=n then
begin
dfs1:=true; exit;
end;
for i:=1 to contact[v0,0] do
if visit[contact[v0,i]]=0 then
begin
visit[contact[v0,i]]:=1;
if dfs1(contact[v0,i]) then
begin
dfs1:=true; exit;
end;
end;
dfs1:=false;
end;
procedure dfs2(v0:integer);
var i:integer;
begin
if repeated then exit;
if visit[v0]=2 then exit;
visit[v0]:=2;
for i:=1 to contact[v0,0] do
begin
if visit[contact[v0,i]]=1 then
begin
repeated:=true; exit;
end;
dfs2(contact[v0,i]);
end;
end;
procedure work;
var i:integer;
begin
for i:=1 to n-1 do
begin
fillchar(visit,sizeof(visit),0);
visit[0]:=1;visit[i]:=1;
repeated:=false;
if not dfs1(0) then
begin
inc(must[0]);must[must[0]]:=i;
dfs2(i);
if not repeated then
begin
inc(middle[0]);middle[middle[0]]:=i;
end;
end;
end;
end;
begin
assign(input,'race3.in');reset(input);
assign(output,'race3.out');rewrite(output);
while not eof do
begin
init;
//writeln(n);
work;
cout_ans;
end;
close(input);
close(output);
end.