P5913 题解

· · 题解

题目分析

一个渐进更优但是在这题数据范围下跟 O({knm\over \omega}) 暴力差不多的做法。

首先我们观察 \text{C-Algae} 的性质，发现这两种操作是对称的，所以有：若 G 为 \text{C-Algae}，则 G 的补图也为 \text{C-Algae}（反之同理），原因是补图可以每次用与原图相反的合并方式造出来。于是我们会了一个暴力做法，即考虑倒推操作，交替进行以下两个拆分步骤，若最终能把图全都拆成单点则说明该图为 \text{C-Algae}。

  1. 把原图分成多个不连通的子图（求连通块），然后分别检查各个子图。

  2. 要么把反图分成多个不连通的子图（求反图连通块），然后分别检查各个子图的反图。

分析时间复杂度。单次操作 1,2 分别是 O(m) 和 O(n^2-m) 的，而操作 2 若能有效会消耗掉至少 O(n) 条边，故至多进行 O({m\over n}) 轮，时间复杂度 O(knm)。

接下来考虑优化拆分的步骤。发现我们应该不同情况差别对待地对操作 1,2 采取不一样的方式求连通块。操作 1 在稀疏图上可以直接枚举边，单次时间复杂度 O(n+m)。而操作 2 的图过于稠密，可以枚举点然后检查不存在的边，因为至多会查到 m 条不存在的边，故单次时间复杂度同样为 O(n+m)。由于 m\leq n^2，故总时间复杂度 O(k(n+m)\times{\min(m,n^2)\over n})=O(k(n+m)\sqrt m)，常数不大，可以通过本题。

代码

实现可见下面代码，感觉还算简洁。

/*
  author: PEKKA_l  
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
#define pb push_back

int T,n,m,u,v;
vector <int> e[10005];
unordered_map <int,int> s;
bool isb(int x,int y) {if(x>y) swap(x,y); return s.count(x*20000+y);}

int zta[10005],ztb[10005],ztc[10005],cntb,cntc,sza[10005],szc[10005];
int nowb[10005],nxt[20005],frm[20005];

queue <int> Q;
void ins(int k,int x) {nxt[nowb[k]]=x; frm[x]=nowb[k]; nowb[k]=x;}
void del(int x) {nxt[frm[x]]=nxt[x]; frm[nxt[x]]=frm[x]; }
void bfs(int x,int k)
{
    Q.push(x); ztb[x]=cntb; ins(ztb[x],x);
    while(!Q.empty())
    {
        int nr=Q.front(); Q.pop();
        for(auto i:e[nr]) {if(!ztb[i]&&zta[i]==k) {ztb[i]=cntb; Q.push(i); ins(ztb[i],i);}}
    }
}
void bfs2(int x,int k)
{
    Q.push(x); ztc[x]=cntc; szc[cntc]++; del(x);
    while(!Q.empty())
    {
        int nr=Q.front(); Q.pop();
        for(int i=nxt[k+10000];i;i=nxt[i])
        {
            if(!isb(nr,i)) {ztc[i]=cntc; szc[cntc]++; del(i); Q.push(i);}
        }
    }
}
void czc(int k) {while(nxt[k+10000]) {int nr=nxt[k+10000]; cntc++; bfs2(nr,k);}}

signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m; s.clear(); for(int i=1;i<=n;i++) e[i].clear();
        for(int i=1;i<=m;i++) {cin>>u>>v; if(u>v) swap(u,v); e[u].pb(v); e[v].pb(u); s[u*20000+v]=1;}
        for(int i=1;i<=n;i++) zta[i]=1; sza[1]=n;
        while(1)
        {
            memset(ztb,0,sizeof(ztb)); cntb=0; for(int i=1;i<=n;i++) nowb[i]=i+10000;
            memset(nxt,0,sizeof(nxt)); memset(frm,0,sizeof(frm));
            for(int i=1;i<=n;i++) if(!ztb[i]) {cntb++; bfs(i,zta[i]);}
            memset(ztc,0,sizeof(ztc)); cntc=0; memset(szc,0,sizeof(szc));
            for(int i=1;i<=cntb;i++) czc(i);
            bool yes=1,no=0;
            for(int i=1;i<=n;i++)
            {
                if(sza[zta[i]]==szc[ztc[i]]) no=1;
                if(szc[ztc[i]]>2) yes=0;
            }
            if(no) {cout<<"NIE"<<endl; break;}
            if(yes) {cout<<"TAK"<<endl; break;}
            memcpy(zta,ztc,sizeof(ztc)); memcpy(sza,szc,sizeof(szc));
        }
    }
}