This post is written in Chinese. Please consider using Google Translate

一道基础的连通分量的图论题。这个题默认了0为起点，N为终点，如果不放心可以再读入的时候判断起点和终点，即入度为0的点为起点，出度为0的点为终点。

该题有两问，第一问很简单，可以尝试去掉每一个点，判断从起点到终点是否有通路，如果没有则该点为“必经点”。

第二问终点在于理解题意。首先可以确定第二问的解集是第一问的子集，所以我们可以第一问得出的每个点深搜，记录下可以到达的点。然后去掉该点，从起点深搜。如果不存在两次深搜皆可到达的点，就说明它是分割点。

/*
ID: cmykrgb1
PROG: race3
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 101
using namespace std;
ifstream fi("race3.in");
ofstream fo("race3.out");

int adjl[MAX][MAX];
int ans[MAX][2];
bool used[MAX],tused[MAX];
int N,start,end;

void init()
{
    int a=0,i=0;
    while (a!=-1)
    {
        fi >> a;
        while (a>=0)
        {
            adjl[i][ ++adjl[i][0] ]=a;
            used[a]=true;
            fi >> a;
        }
        i++;
    }
    N=i-2;
    for (i=0;i<=N;i++)
    {
        if (adjl[i][0]==0)
            end=i;
        if (!used[i])
            start=i;
    }
}

void dfs3(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!tused[j])
        {
            tused[j]=true;
            dfs3(j);
        }
    }
}

void dfs2(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!used[j])
        {
            used[j]=true;
            dfs2(j);
        }
    }
}

void question2()
{
    int i,j,k;
    for (i=1;i<=N-1;i++)
    {
        memset(used,0,sizeof(used));
        memset(tused,0,sizeof(tused));
        dfs2(i);
        tused[i]=true;
        tused[0]=true;
        dfs3(0);
        k=1;
        for (j=0;j<=N;j++)
            if (j!=i && used[j] && tused[j])
            {
                k=0;
                break;
            }
        if (k)
            ans[ ++ans[0][1] ][1]=i;
    }
}

void dfs1(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!used[j])
        {
            used[j]=true;
            dfs1(j);
        }
    }
}

void question1()
{
    int i;
    for (i=1;i<=N-1;i++)
    {
        memset(used,0,sizeof(used));
        used[i]=true;
        dfs1(0);
        if (!used[N])
            ans[ ++ans[0][0] ][0]=i;
    }
}

void print()
{
    int i;
    fo << ans[0][0];
    for (i=1;i<=ans[0][0];i++)
        fo <<' ' << ans[i][0];
    fo << endl;
    fo << ans[0][1];
    for (i=1;i<=ans[0][1];i++)
        fo <<' ' << ans[i][1];
    fo << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    question1();
    question2();
    print();
    return 0;
}