🔍 解题思路

这里提供一种更简洁的写法，不过思想大同小异。

主要分两步。

首先起点bfs一波，看i是不是必经点。

然后不用再搜索了，因为第一张子图的点集已确定，第二张子图的也就显而易见，遍历这个点集，假如有连向起点子图的就不满足。

//By: Sirius_Ren
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int tot=1,first[51],cnt,v[101],nxt[101],n,vis[51],ansx=0,ansy=0,j,k;
queue<int> p,q,r;
void add(int x,int y){v[tot]=y,nxt[tot]=first[x],first[x]=tot++;}
int main()
{
    memset(first,-1,sizeof(first));
    for(cnt=0;~n;cnt++)
        while(scanf("%d",&n)&&n>=0)add(cnt,n);
    cnt--;
    for(int i=1;i<cnt;i++){
        memset(vis,0,sizeof(vis));
        q.push(0);vis[i]=1;
        while(!q.empty()){
            int t=q.front();q.pop();
            vis[t]=1;
            for(int l=first[t];~l;l=nxt[l])
                if(!vis[v[l]])q.push(v[l]);
        }
        if(!vis[cnt]){
            ansx++,p.push(i);
            for(j=0;j<=cnt;j++)
                if(!vis[j]||j==i)
                    for(k=first[j];~k;k=nxt[k])
                        if(vis[v[k]]&&v[k]!=i)goto end;
            ansy++,r.push(i);
            end:;
        }
    }
    printf("%d",ansx);
    while(!p.empty())printf(" %d",p.front()),p.pop();
    printf("\n");
    printf("%d",ansy);
    while(!r.empty())printf(" %d",r.front()),r.pop();
}