cdqppt地址：https://wenku.baidu.com/view/a2bf4ad9ad51f01dc281f1df.html；
代码实现参考的http://blog.csdn.net/u014609452/article/details/51447533；
这个代码实现还是很妙的，为了快速找到label值最大的节点，新建虚拟节点n+1+i，连向所有label等于i的点；
#include#include #include #include #include using namespace std;const int maxn=1005,maxm=5000005;struct edg{ int to,nxt;}e[maxm];int f[maxn],best,n,m,last[maxn<<1],t,vis[maxn],seq[maxn];void add(int x,int y){++t;e[t].nxt=last[x];last[x]=t;e[t].to=y;}void mcs(){ for(int i=1;i<=n;++i) add(n+1,i); for(int s=n;s;--s){ while(1){ int v=0; for(int i=last[n+1+best];i&&!v;i=e[i].nxt){ if(!vis[e[i].to]){ v=e[i].to; } else last[best+n+1]=e[i].nxt; } if(v){ vis[v]=1;seq[s]=v; for(int i=last[v];i;i=e[i].nxt) if(!vis[e[i].to]){ f[e[i].to]++; add(f[e[i].to]+n+1,e[i].to); best=max(best,f[e[i].to]); } break; } else best--; } }}bool can[maxn][maxn];int rk[maxn],x,y,cnt,tmp[maxn];int main(){ cin>>n>>m; for(int i=1;i<=m;++i){ scanf("%d%d",&x,&y); add(x,y);add(y,x); can[x][y]=can[y][x]=1; } mcs(); for(int i=1;i<=n;i++)rk[seq[i]]=i; for(int i=n;i;i--){ int x=seq[i];cnt=0; for(int j=last[x];j;j=e[j].nxt){ if(rk[e[j].to]>rk[x])tmp[++cnt]=rk[e[j].to]; } sort(tmp+1,tmp+cnt+1); for(int i=2;i<=cnt;++i){ if(!can[seq[tmp[1]]][seq[tmp[i]]]) {puts("Imperfect\n");return 0;} } } printf("Perfect\n"); return 0;}