链接

弦图求最大独立集

显然求出完美消除序列后，我们直接贪心的从第一个点开始选，选到不能选为止，选出的个数就是最大的答案

/*  Never Island  */
/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
int lis[210],pos[210],n,m,vis[210];
int mmp[210][210],cnt,head[210],ans[210],t[210];
struct edge
{
    int next,to;    
}e[40010];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
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;
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);
    }
    for(int i=1;i<=n;i++)
    {
        q.push(node(0,i));
    }
    cnt=n;
    while(!q.empty())
    {
        node u=q.top();
        q.pop();
        if(!vis[u.id])
        {
            lis[cnt]=u.id;
            pos[u.id]=cnt--;
            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.id=v,u.ind=ans[v];
                    q.push(u);
                } 
            }
        }
    }
    int rans=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        int u=lis[i];
        cnt=0;
        if(!vis[u])
        {
            rans++;
            vis[u]=1;
        }
        else
        {
            continue;
        }
        for(int j=head[u];j;j=e[j].next)
        {
            int v=e[j].to;
            vis[v]=1;
        }
    }
    cout<<rans;
    return 0;
}