현도 완벽 제거 시퀀스 MCS 알고리즘

일반 그림 의 두 가지 성질 에 대해:
최대 단 수 ≤ 최소 색 수 최대 독립 집합 ≤ 최소 단 커버
현 도 는:
최대 그룹 수 = 최소 색상 수 최대 독립 집합 = 최소 그룹 덮어 쓰기 (무슨 소 용이 있 는 지 모 르 겠 지만
완벽 제거 시퀀스:
서열 중의 점 vi 에 대해 vi 뒤에 배열 되 고 vi 와 연 결 된 점 은 하나의 그림 에 완벽 한 제거 서열 이 존재 하 는 것 이 현 그림 의 충전 조건 이다.
그렇다면 서열 을 완벽 하 게 없 애 는 것 은 무슨 소 용이 있 습 니까? 용도 가 큽 니 다. 현도 의 최대 단수 / 최소 색 수 를 구 할 때 는 서열 을 완벽 하 게 없 애 는 데 있어 서 뒤에서 욕심 을 내 서 염색 하면 됩 니 다. 최대 독립 집 / 최소 단 을 구 할 때 는 서열 을 완벽 하 게 없 애 는 데 있어 서 앞으로 욕심 을 내 면 됩 니 다.
그러면 일련의 문제 가 발생 했다. 먼저 현도 의 판정 이다. 우 리 는 이 그림 이 완벽 하 게 서열 을 없 앴 는 지 확인 해 야 한다.
MCS 알고리즘
다음 에서 앞으로 서열 을 정 하 는 점 은 점 하 나 를 가 져 올 때마다 서열 에 들 어가 지 않 은 점 의 레이 블 + 1 을 가 져 옵 니 다. 점 을 가 져 올 때마다 레이 블 의 가장 큰 점 중 하 나 를 선택 합 니 다. 구체 적 으로 설명 하기 어렵 습 니 다. 말 하고 싶 지 않 습 니 다. = 아래 에 코드 가 있 습 니 다. 복잡 도 O (m + n)
그림 이 현도 라면 이 알고리즘 이 구 한 서열 이 완벽 하 게 서열 을 없 앨 수 있다 고 합 니 다. 그러면 우리 가 현 도 를 판단 해 야 할 때 이 서열 이 완벽 하 게 서열 을 없 애 는 지 판단 해 야 합 니 다. 판단 방법 은 뒤에서 서열 중의 모든 점 v 가 조건 을 만족 시 키 는 지 확인 하 는 것 입 니 다. v 뒤에 있 는 점 집합 은 N (v) 으로 기록 하 는 것 입 니 다.가운데 줄 의 맨 앞 점 은 next (v) 가 N (v) 의 다른 점 과 연결 되 어 있 는 지 여 부 를 기록 합 니 다. 구체 적 으로 는 포인트 가 적 으 면 인접 행렬 로 O (m + n) 를 판단 하고 포인트 가 많 으 면 사 이 드 시트 를 정렬 한 다음 2 분 O (mlogm + n) 를 판단 합 니 다.
이로써 우 리 는 현도 판정 문 제 를 어떻게 해결 하고 서열 을 완벽 하 게 없 애 는 지 알 게 되 었 다. 그렇다면 구체 적 인 예 제 를 살 펴 보 자.
zoj1015:
누 드 의 현도 판정, 포인트 1000, 직접 위의 방법 에 따라 마구 잡 이 로 하면 코드 가 됩 니 다.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iomanip>
#include<vector>
#include<set>
#include<map>
#include<queue>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#define rep(i,k,n) for(int i=(k);i<=(n);i++)
#define rep0(i,n) for(int i=0;i<(n);i++)
#define red(i,k,n) for(int i=(k);i>=(n);i--)
#define sqr(x) ((x)*(x))
#define clr(x,y) memset((x),(y),sizeof(x))
#define pb push_back
#define mod 1000000007
const int maxn=1010;
const int maxm=3500010;

struct List
{
    int v,next;
}list[maxm];
int eh[maxn],tot,mh[maxn];

inline void add(int h[],int u,int v)
{
    list[tot].v=v;
    list[tot].next=h[u];
    h[u]=tot++;
}

int n,m,best;
int q[maxn],f[maxn],g[maxn];
bool vis[maxn];

void MCS()
{
    clr(mh,-1);clr(vis,0);clr(f,0);
    for(int i=1;i<=n;i++)add(mh,0,i);
    best=0;
    for(int j=n;j;j--)
    {
        while(1)
        {
            int i;
            for(i=mh[best];~i;i=list[i].next)
            {
                if(!vis[list[i].v])break;
                else mh[best]=list[i].next;
            }
            if(~i)
            {
                int x=list[i].v;
                q[j]=x;g[x]=j;
                vis[x]=1;
                for(i=eh[x];~i;i=list[i].next)if(!vis[list[i].v])
                {
                    f[list[i].v]++;
                    add(mh,f[list[i].v],list[i].v);
                    best=max(best,f[list[i].v]);
                }
                break;
            }
            else best--;
        }
    }
}

int st[maxn],top;
bool e[maxn][maxn];

bool checkq()
{
    for(int j=n-1;j;j--)
    {
        int u=q[j];
        top=0;
        int ming=n+1,minv;
        for(int i=eh[u];~i;i=list[i].next)if(g[list[i].v]>j)
        {
            st[++top]=list[i].v;
            if(g[list[i].v]<ming)
            {
                ming=g[list[i].v];
                minv=list[i].v;
            }
        }
        if(ming==n+1)continue;
        for(int i=1;i<=top;i++)if(st[i]!=minv)
        {
            if(!e[minv][st[i]])return 0;
        }
    }
    return 1;
}

int main()
{
    while(scanf("%d%d",&n,&m),n)
    {
        clr(eh,-1);tot=0;
        clr(e,0);

        int u,v;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(eh,u,v);
            add(eh,v,u);
            e[u][v]=e[v][u]=1;
        }

        MCS();
        puts(checkq()?"Perfect":"Imperfect");
        puts("");
    }

    return 0;
}

bzoj1006:
누 드 스 트 라 이 프 의 최소 염색 수 는 위 에서 만 드 는 대로 함부로 하면 코드 가 됩 니 다.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iomanip>
#include<vector>
#include<set>
#include<map>
#include<queue>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#define rep(i,k,n) for(int i=(k);i<=(n);i++)
#define rep0(i,n) for(int i=0;i<(n);i++)
#define red(i,k,n) for(int i=(k);i>=(n);i--)
#define sqr(x) ((x)*(x))
#define clr(x,y) memset((x),(y),sizeof(x))
#define pb push_back
#define mod 1000000007
const int maxn=10010;
const int maxm=4000010;

struct List
{
    int v,next;
}list[maxm];
int eh[maxn],tot,mh[maxn];

inline void add(int h[],int u,int v)
{
    list[tot].v=v;
    list[tot].next=h[u];
    h[u]=tot++;
}

int n,m,best,q[maxn],f[maxn],color[maxn],mark[maxn];
bool vis[maxn];

void MCS()
{
    clr(mh,-1);clr(vis,0);clr(f,0);
    rep(i,1,n)add(mh,0,i);
    best=0;
    red(j,n,1)
    {
        while(1)
        {
            int i;
            for(i=mh[best];~i;i=list[i].next)
            {
                if(!vis[list[i].v])break;
                else mh[best]=list[i].next;
            }
            if(~i)
            {
                int x=list[i].v;
                q[j]=x;vis[x]=1;
                for(i=eh[x];~i;i=list[i].next)
                {
                    int v=list[i].v;
                    if(vis[v])continue;
                    f[v]++;
                    add(mh,f[v],v);
                    best=max(best,f[v]);
                }
                break;
            }
            else best--;
        }
    }
}


int main()
{
    scanf("%d%d",&n,&m);
    int u,v;
    clr(eh,-1);tot=0;
    rep(i,1,m)
    {
        scanf("%d%d",&u,&v);
        add(eh,u,v);
        add(eh,v,u);
    }
    MCS();
    clr(mark,0);clr(color,0);
    int ans=0;
    red(j,n,1)
    {
        for(int i=eh[q[j]];~i;i=list[i].next)mark[color[list[i].v]]=j;
        int i;
        for(i=1;mark[i]==j;i++);
        color[q[j]]=i;
        ans=max(ans,i);
    }
    printf("%d
",ans);

    return 0;
}

구체 적 으로 최대 독립 집합 과 최소 그룹 커버 를 구 하 는 것 은 주로 완벽 하 게 서열 을 없 애 는 것 이다. 나머지 물건 도 많 지 않 고 잠시 문 제 를 찾 지 못 해서 상세 하 게 말 하지 않 는 다.
또한, 현 도 를 찾 는 모든 큰 연대 의 문제 도 있 습 니 다. 여기 서 는 위 에서 말 한 N (v) 과 next (v) 를 사용 해 야 합 니 다. 분명 큰 단 은 v * 8746 ° N (v) 의 형식 일 것 입 니 다. 그러면 큰 단 인지 아 닌 지 를 판단 하여 하나의 w 가 존재 하 는 지 판단 하면 next (w) = v 를 만족 시 키 고 | N (v) | + 1 ≤ | N (w) | 복잡 도 는 O (m + n) 라 고 합 니 다. 잠시 연구 한 적 이 없습니다.