[TIOJ 1684] 圓桌武士 Knights of the Round Table

這題用到了點雙連通分量(元件)，可以看看資訊之芽的教學，我覺得寫得還蠻詳細的。

作法：

能夠圍在圓桌上就代表他們滿足相鄰不連邊，且個數是奇數，所以如果考慮仇視關係的補圖的話，就是補圖上的奇圈，所以題目變成要求所有不在補圖的任何一個奇圈中的點。

到這裡我就卡了很久，我一開始是想先用類似拓樸排序的過程一直把度為 1 的點拔掉，還有如果圖裡面有橋的話也可以直接拔掉，那麼這樣我們就可以先確定每個連通塊裡面都有一個圈( 因為每個點的度都>=2 )。如果這個連通塊裡沒有奇圈，那麼就作完了，如果有的話呢 ? 這樣如果有連通塊中的一個點 P ，他有兩條可以走到這個奇圈上不同點的路徑 ( 也就是存在奇圈上的兩點 A , B 滿足 A!=B ，且P可以走到A和B )，那麼 P 也一定在一個奇圈裡面，因為A和B恰好把這個奇圈分成一條偶數長的路徑和一條奇數長的路徑，選其中一條加上 A -> P -> B 的路徑一定可以。

但在邊雙連通分量中沒辦法保證每個點都有這個性質，舉個最簡單的例子就是兩個圈共用了一個點。但觀察這個例子會發現，他們共用的點不就是割點嗎！所以如果考慮點雙連通分量呢 ? 這樣就會發現對每個在分量裡面的 P 都有上面那個性質了！詳細證明也不難證，由點雙連通的定義就可以得到了。

所以我們只要先找出所有的點雙連通分量，然後看每個分量裡面有沒有奇圈就好了( 再一次DFS著色 )。在我的認知裡，「一個點雙連通分量」是「一組邊的集合」，就如同資芽的影片裡講的，所以我在找點雙連通分量時是先找邊，最後要處理的這個連通分量裡的點就是這些邊的端點的聯集。但這裡的作法似乎是直接找到點雙連通元件的點集，我不知道這樣處理會不會有問題，所以就沒試著寫寫看了。不過這樣可以把兩次DFS壓成一次，真是太神了！！ <(_ _)>

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10,maxm=500000+10 ;
 
struct P{int x,y;};
vector<int> v[maxn] ;
vector<P> edge ;
 
int lev[maxn],bcnt ;
vector<int> vb[maxm] ;
int adj[maxn][maxn] ;
bool vis[maxn],ans[maxn] ;
bool vis_e[maxm] ;
stack<int> st ;
 
int dfs(int x,int l)
{
    int low ;
    vis[x]=1 ; low=lev[x]=l ;
    for(auto i : v[x])
    {
        if(vis_e[i]) continue ;
        vis_e[i]=1 ; st.push(i) ;
 
        int to= (edge[i].x==x ? edge[i].y : edge[i].x) ;
        if(vis[to]) low=min(low,lev[to]) ;
        else
        {
            int low2=dfs(to,l+1) ;
            low=min(low,low2) ;
            if(low2>=lev[x])
            {
                bcnt++ ; vb[bcnt].clear() ;
                while(1)
                {
                    int t=st.top() ; st.pop() ;
                    vb[bcnt].push_back(t) ;
                    if(t==i) break ;
                }
            }
        }
    }
    return low ;
}
 
int col[maxn] ;
bool dfs2(int x,int c)
{
    col[x]=c ;
    for(auto i : v[x])
    {
        int to= edge[i].x==x ? edge[i].y : edge[i].x ;
        if(col[to]==c || (col[to]==-1 && !dfs2(to,c^1))) return 0 ;
    }
    return 1 ;
}
 
int tmp[maxm] ;
main()
{
    int n,m,tc ;
    while(scanf("%d%d",&n,&m)==2 && m+n && ++tc)
    {
        for(int i=1;i<=n;i++) v[i].clear() ;
        edge.clear() ;
        for(int i=0;i<m;i++)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            adj[x][y]=adj[y][x]=tc ;
        }
        for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
            if(adj[i][j]!=tc)
        {
            edge.push_back((P){i,j}) ;
            int s=edge.size() ;
            v[i].push_back(s-1) ;
            v[j].push_back(s-1) ;
        }
 
        bcnt=0 ;
        memset(ans,0,sizeof(ans)) ;
        memset(vis,0,sizeof(vis)) ;
        memset(vis_e,0,sizeof(vis_e)) ;
        for(int i=1;i<=n;i++) if(!vis[i] && !v[i].empty())
        {
            while(!st.empty()) st.pop() ;
            dfs(i,0) ;
        }
 
        for(int i=1;i<=bcnt;i++)
        {
            int sz=0 ;
            for(auto j : vb[i])
                tmp[sz++]=edge[j].x , tmp[sz++]=edge[j].y ;
            for(int j=0;j<sz;j++) v[tmp[j]].clear() , col[tmp[j]]=-1 ;
            for(auto j : vb[i])
                v[edge[j].x].push_back(j) ,
                v[edge[j].y].push_back(j) ;
            if(!dfs2(tmp[0],0))
                for(int j=0;j<sz;j++) ans[tmp[j]]=1 ;
        }
        printf("%d\n",count(ans+1,ans+n+1,false)) ;
    }
}