记录编号	78143	评测结果	AAAAAWAAWAW
题目名称	891.街道赛跑	最终得分	72
用户昵称	cstdio	是否通过	未通过
代码语言	C++	运行时间	0.004 s
提交时间	2013-11-03 14:48:20	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZEN=101;
vector<int> c[SIZEN];
vector<int> onlyway,cut;
bool nowable[SIZEN]={0};
int n;
void DFS(bool flag[SIZEN],int x){
	if(!nowable[x]) return;
	if(flag[x]) return;
	flag[x]=true;
	int i;
	for(i=0;i<c[x].size();i++) DFS(flag,c[x][i]);
}
void work(void){
	int i,j;
	bool canreach_start[SIZEN];
	bool canreach_middle[SIZEN];
	for(i=1;i<n;i++){
		memset(nowable,1,sizeof(nowable));
		memset(canreach_start,0,sizeof(canreach_start));
		nowable[i]=false;
		DFS(canreach_start,0);
		if(!canreach_start[n]){
			onlyway.push_back(i);
			memset(canreach_middle,0,sizeof(canreach_middle));
			nowable[i]=true;
			DFS(canreach_middle,i);
			//for(j=0;j<=n;j++) cout<<canreach_start[j]<<" ";cout<<endl;
			//for(j=0;j<=n;j++) cout<<canreach_middle[j]<<" ";cout<<endl;
			for(j=1;j<n;j++){
				if(j==i) continue;
				if(!(canreach_middle[j]^canreach_start[j])){
					//cout<<i<<" "<<j<<endl;
					goto END;
				}
			}
			cut.push_back(i);
		}
		END:;
	}
	printf("%d ",onlyway.size());
	for(i=0;i<onlyway.size();i++) printf("%d ",onlyway[i]);
	printf("\n");
	printf("%d ",cut.size());
	for(i=0;i<cut.size();i++) printf("%d ",cut[i]);
	printf("\n");
}
void read(void){
	n=0;
	int i=0,x;
	while(true){
		do{
			scanf("%d",&x);
			if(x==-1) return;
			c[i].push_back(x);
		}while(x!=-2);
		n=i++;
	}
}
int main(){
	freopen("race3.in","r",stdin);
	freopen("race3.out","w",stdout);
	read();
	work();
	return 0;
}