题解 SP5446 【FISHNET - Fishing Net】

· · 题解

弦图判定问题

团的定义是无向图中的一个子图，并且为完全图

弦的定义为，连接环内两个不相邻点的边，弦图的定义是，任意大于三的环都至少有一条弦，那么弦图中所有的极小团的大小都是3

一些点诱导子图定义为不含其他边的子图

若与点v相邻的点集S_v+v的诱导子图为一个团，则v是一个单纯点

然后此题要判定一张图是不是弦图，就要引入完美消除序列的概念，即n个点的一种排列v_1,v_2..v_n满足，v_i在v_{i+1}..v_n的诱导子图中为单纯点

可以证明一张图是弦图的充要条件是其拥有完美消除序列

完美消除序列常用的求法为MCS最大势算法，按n..1的顺序给点标号，每次标号的点是当前与已标号点集S_n中相邻点最多的点，可以链表优化至线性，常用的还有堆优化的O(nlogn)求法

判断一个序列是否为完美消除序列，只需要对于任意一个点v_i，我们找到他之后的序列中的和他相邻的点，称作点集S_v，如果S_v中最小的元素与其他元素都相邻，则该序列为完美消除序列，否则不是

证明可以看cdq的ppt

然后这题有点坑...要输出两个换行，样例还错了，将就做吧

/*  Never Island  */
/*deco loves Chino*/
/* Summer Pockets */
#include <bits/stdc++.h>
using namespace std;
int head[1010],lis[1010],cnt,tot,vis[1010],ans[1010],t[1010],pos[1010];
int mmp[1010][1010],n,m;
struct node
{
    int ind,id;
    node(int A,int B):ind(A),id(B){}
    bool operator<(const node&a)const
    {
        return ind<a.ind;
    }
};
priority_queue<node> q;
struct edge
{
    int next,to;
}e[2000010];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int main()
{
    while(cin>>n>>m,n!=0)
    {
        memset(lis,0,sizeof(lis));
        memset(pos,0,sizeof(pos));
        memset(mmp,0,sizeof(mmp));
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(ans,0,sizeof(ans));
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
            mmp[x][y]=mmp[y][x]=1;
        }
        for(int i=n;i>=1;i--)
        {
            mmp[i][i]=1;
            q.push(node(0,i));
        }
        tot=n;
        while(!q.empty())
        {
            node u=q.top();
            q.pop();
            if(!vis[u.id])
            {
                lis[tot--]=u.id;
                pos[u.id]=tot+1;
                vis[u.id]=1;
                for(int i=head[u.id];i;i=e[i].next)
                {
                    int v=e[i].to;
                    if(!vis[v])
                    {
                        ans[v]++;
                        u.ind=ans[v],u.id=v;
                        q.push(u);
                    }
                }
            }
        }
        memset(vis,0,sizeof(vis));
        int flag=0;
        for(int i=n;i>=1;i--)
        {
            int u=lis[i],mn=n;
            cnt=0;
            vis[u]=1;
            for(int j=head[u];j;j=e[j].next)
            {
                int v=e[j].to;
                if(vis[v])
                {
                    mn=min(mn,pos[v]);
                    t[++cnt]=v;
                }
            }
            if(n==mn)
            {
                continue;
            }
            for(int j=1;j<=cnt;j++)
            {
                if(!mmp[lis[mn]][t[j]])
                {
                    cout<<"Imperfect"<<"\n\n";
                    flag=1;
                    break;
                }
            }
            if(flag)
            {
                break;
            }
        }
        if(!flag)
        {
            cout<<"Perfect"<<"\n\n";
        }

    }
    return 0;
}