TIOJ 1256 砲打皮皮4 [Graph]

poao899    1900K    166MS    G++     1.72K     2009-11-19 23:06:02                        .

好慚愧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]);
		}
	}
}