圖論的題目，主要考察的是聯(lián)通性的問(wèn)題。
由于數(shù)據(jù)非常弱小，枚舉+遍歷驗(yàn)證即可。
時(shí)間O（nm）
代碼
/*
USER:zyn19961
TASK:race3
LANG:C++
*/
#include<cstdio>
#include<cstring>
const int maxm=105;
int next[maxm];
int head[maxm];
int to[maxm];
bool arrived[maxm];
bool count[maxm];
int begin,end;
int n=0,m=0;
int ans1[maxm];
int ans2[maxm];
void dfs(int i);
int main(){
freopen("race3.in","r",stdin);
freopen("race3.out","w",stdout);
memset(ans1,0,sizeof(ans1));
memset(ans2,0,sizeof(ans2));
memset(head,0,sizeof(head));
memset(next,0,sizeof(next));
memset(to,0,sizeof(to));
int t;
while(1){
while(1){
scanf("%d",&t);
if(t==-2||t==-1)
break;
m++;
next[m]=head[n];
head[n]=m;
to[m]=t;
}
if(t==-1)
break;
n++;
}
n--;
for(int i=1;i<=n-1;i++){
memset(arrived,false,sizeof(arrived));
memset(count,false,sizeof(count));
arrived[i]=true;
dfs(0);
if(!arrived[n]){
ans1[0]++;
ans1[ans1[0]]=i;
for(int j=0;j<=n;j++)
if(arrived[j])
count[j]=true;
count[i]=false;
memset(arrived,false,sizeof(arrived));
dfs(i);
bool flag=true;
for(int j=0;j<=n;j++)
if(arrived[j]&&count[j])
flag=false;
if(flag){
ans2[0]++;
ans2[ans2[0]]=i;
}
}
}
printf("%d",ans1[0]);
for(int i=1;i<=ans1[0];i++)
printf(" %d",ans1[i]);
printf("\n");
printf("%d",ans2[0]);
for(int i=1;i<=ans2[0];i++)
printf(" %d",ans2[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}
void dfs(int i){
arrived[i]=true;
for(int p=head[i];p;p=next[p])
if(!arrived[to[p]])
dfs(to[p]);
}