현도 ZOJ 1015 Fishing Net 판정 방법

문 제 를 푸 는 사고:1 현 도 를 보고 주말 에 나무 가 있 습 니 다!너무 약해 서 알고리즘 은 CDQ 의 PPT 에서 준 최대 세 알고리즘(MCS)에 따라 완벽 한 제거 서열 을 구 합 니 다.앞 뒤 sumbit 19 번,WA 에 엄 청 난 분 모 를 제 공 했 는데...................................................많이 써 서 백업 해 주세요.2 유용 한 자료:  3 정리:하나의 그림 은 현 그림 이 고 완벽 한 제거 서열 이 있다 고 생각 합 니 다.그래서 먼저 완벽 한 제거 서열 을 구 해 야 한다.
4.567916.4.구 한 것 이 완벽 한 제거 서열 인지 아 닌 지 를 어떻게 판단 합 니까?
코드 붙 이기:(V*V 의 복잡 도...)

 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
const int maxn=1000+10; 
int gra[maxn][maxn]; 
int n, m; 
int label[maxn], temp[maxn], num[maxn]; 
void numberVertex() 
{ 
int i, j; 
//label[n]=0, num[n]=1; 
for(i=n; i>=1; i--) 
{ 
int mm=-1, pos; 
for(j=1; j<=n; j++) 
{ 
if( !num[j] && label[j]>mm) 
{ 
mm=label[j]; 
pos=j; 
} 
} 
num[pos]=i; 
for(j=1; j<=n; j++) 
{ 
if( !num[j] && ( gra[pos][j] || gra[j][pos] ) ) 
label[j]++; 
} 
} 
return ; 
} 
int check() 
{ 
int i, j, flag=1; 
for(i=1; i<=n && flag; i++) 
{ 
memset(temp,0,sizeof(temp)); 
int len=0; 
for(j=1; j<=n; j++) 
{ 
if( num[i]<num[j] && gra[ i ][ j ] ) 
{ 
temp[len++]=j; 
} 
} 
for(j=1; j<len; j++)//  WA      。。。 
if(num[ temp[0] ]>num[ temp[j] ]) 
swap(temp[0], temp[j]); 
for(j=1; j<len; j++) 
if( !gra[ temp[0] ][ temp[j] ] ) 
{ 
flag=0; 
break; 
} 
} 
return flag; 
} 
int main() 
{ 
while( scanf("%d %d",&n,&m)!=EOF ) 
{ 
if(n==0 && m==0) 
break; 
memset(label,0,sizeof(label)); 
memset(num,0,sizeof(num)); 
memset(gra,0,sizeof(gra)); 
for(int i=0; i<m; i++) 
{ 
int x, y; 
scanf("%d %d",&x, &y); 
gra[x][y]=gra[y][x]=1; 
} 
numberVertex(); 
if( check() ) 
puts("Perfect
"); 
else 
puts("Imperfect
"); 
} 
return 0; 
}