好慚愧QQ
這題只是複製TIOJ 1137 4.收費站設置問題的code當初只想用分帳玩一下開錯就AC了
蚯蚓：不是很明顯是AP點嗎
//*********************************
#include<stdio.h>
#include<algorithm>
#define MAX 200200
#define MAXV 10010
int getint(){
int g=0,c=getchar();
while(c==10||c==32||c==9)c=getchar();
while(c>='0'&&c<='9'){
g=g*10+c-48;
c=getchar();
}
return g;
}
struct Edge{
int j;
Edge *next;
}E[MAX],*V[MAXV];
int edgeCnt,APCnt;
int dateBack[MAXV];
int AP[MAXV],ttime;
int visited[MAXV];
int t,n,m,a,b;
void setEdge(int i,int j){
Edge *p,*now;
p=V[i];
V[i]=&E[++edgeCnt];
E[edgeCnt].j=j;
E[edgeCnt].next=p;
p=V[j];
V[j]=&E[++edgeCnt];
E[edgeCnt].j=i;
E[edgeCnt].next=p;
}
int FindAP(int now,int depth){
Edge *p=V[now];
int next,count=0;
bool isAP=0;
visited[now]=++ttime;
dateBack[now]=2147483647;
while(p!=NULL){
next=p->j;
if(!visited[next]){
count++;
int son=FindAP(next,depth+1);
if(son>=visited[now]){
dateBack[now]=son;
if(depth){
isAP=1;
}
}
dateBack[now]<?=son;
}
else{
dateBack[now]<?=visited[next];
}
p=p->next;
}
if(depth==0&&count>1 || isAP){
AP[APCnt++]=now;
}
return dateBack[now];
}
int caseCnt;
main(){
while(scanf("%d%d",&n,&m),n+m){
//Initialize
for(int i=0;i<MAXV;i++){
visited[i]=0;
V[i]=NULL;
}
edgeCnt=-1;APCnt=0;ttime=0;
//Construct a graph
for(int i=0;i<m;i++){
a=getint();
b=getint();
setEdge(a,b);
}
//Find AP
for(int i=1;i<=n;i++)
if(!visited[i])
FindAP(i,0);
//Output
std::sort(AP,AP+APCnt);
printf("Case #%d:",++caseCnt);
printf("%d ",APCnt);
if(!APCnt)puts("0");
for(int i=0;i<APCnt;i++,putchar(i==APCnt?'\n':32)){
printf("%d",AP[i]);
}
}
}
