[bzoj1242] Zju1015 Fishing Net弦图判定

　　弦图判定。。MCS算法。

　　先选一个点，然后每次拿 相邻已选点最多 的未选点。

　　选完之后判断一下是否是完美消除序列。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 using namespace std;

 const int maxn=;

 struct zs{int too,pre;}e[];int tot,last[maxn<<];

 bool con[maxn][maxn],u[maxn];

 int st[maxn],top,dl[maxn],tim[maxn],deg[maxn];

 int i,j,k,n,m,now;

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 inline void ins(int a,int b){e[++tot].too=b,e[tot].pre=last[a],last[a]=tot;}

 #define f(x) x+n+1

 inline void mcs(){

     register int j;int i,mx=,pos;

     for(i=;i<=n;i++)ins(f(),i);

     for(i=n;i;i--){

         pos=;

         for(j=last[f(mx)];j&&!pos;j=e[j].pre)

             if(!u[e[j].too])pos=e[j].too,u[pos]=,dl[i]=pos;

             else last[f(mx)]=e[j].pre;

         if(!pos)mx--,i++;else{

             for(j=last[pos];j;j=e[j].pre)if(!u[e[j].too])

                 deg[e[j].too]++,ins(f(deg[e[j].too]),e[j].too),mx=max(mx,deg[e[j].too]);

         }

     }

 }

 bool cmp(int a,int b){return tim[a]<tim[b];}

 int main(){

     n=read(),m=read();register int j;

     for(i=;i<=m;i++)j=read(),k=read(),ins(j,k),ins(k,j),con[j][k]=con[k][j]=;

     for(i=;i<=n;i++)con[i][i]=;

     mcs();

     for(i=;i<=n;i++)tim[dl[i]]=i;tim[]=1e9;

     for(i=n;i;i--){

         now=dl[i],top=;

         for(j=last[now];j;j=e[j].pre)if(tim[e[j].too]>i)

             st[++top]=e[j].too;

         if(top<)continue;int mn=;

         for(j=;j<=top;j++)if(tim[st[j]]<tim[mn])mn=st[j];

         for(j=;j<=top;j++)if(!con[st[]][st[j]]){

             puts("Imperfect");return ;

         }

     }

     puts("Perfect");

 }