Loading...

bzoj 1242 弦图判定

check评论:0 条 remove_red_eye浏览量:62 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-18

链接

给你一张无向图,让你判断他是不是弦图

首先如果一个图是弦图的充要条件是他有完美消除序列

那么我们就可以用最大势算法先求出这个序列

关于判断他是不是完美消除序列,一种方法是暴力判断单纯点,但是很慢

我们考虑对于这个序列$v_1,v_2...v_n$,如果对于第$i$个点$v_i$与他相连的点$v_{k1},v_{k2}...v_{kp}$,满足$\forall v_{kq} q\in [1,p] , kq \in [i+1,n] , kq < k(q+1)$,我们只需要判断$v_{k1}$是否和其他点相连即可

尤其注意,最大势求出来序列的编号从$n$开始递减

最大势写的$nlogn$..所以总复杂度$nlogn$

/*  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()
{
    cin>>n>>m;
    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));
    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";
                return 0;
            }
        }
    }
    cout<<"Perfect";
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名