自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 21:41:10，当前版本为作者最后更新于2018-05-23 21:53:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看楼下大佬们代码及其长，我这里提供一种更简洁的写法，不过思想大同小异。

主要分两步。

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

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

#include<iostream>
#include<cstdio>
#define N 100
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,x,u,g[N][N],in[N],l,r,q[N],ans[N],mus[N],yes;
int main(){
	scanf("%d",&x);
	while(x!=-1){
		while(x!=-2 && x!=-1) g[n][x]=1,scanf("%d",&x);
		scanf("%d",&x),n++;
	}n--,in[0]=1;
	FOR(i,1,n-1){
		FOR(v,1,n) in[v]=0;
	    l=1,r=2;
	    while(l<r){
		    u=q[l++];
		    FOR(v,0,n) if(g[u][v] && in[v]==0 && v!=i)
			    in[v]=1,q[r++]=v;
	    }if(in[n]==0){
			mus[++mus[0]]=i,yes=1;
			FOR(v,0,n)if(!in[v])
			FOR(w,0,n)if(g[v][w] && in[w]) yes=0;
			if(yes) ans[++ans[0]]=i;
		}
	}
	FOR(i,0,mus[0]) printf("%d ",mus[i]);printf("\n");
	FOR(i,0,ans[0]) printf("%d ",ans[i]);
}```