训练指南 UVALive - 3523 （双连通分量 + 二分图染色）

Diposting di | Edited on

Knights of the Round Table

UVALive - 3523

题意

圆桌骑士。有的骑士之间是相互憎恨的，不能连坐，需要安排奇数个骑士围着桌子坐着，大于3个，求哪些骑士不可能安排到座位。

根据给定的关系，如果两个骑士之间没有憎恨关系，那么连边。最终就是求有多少个点无法位于奇圈之内。根据二分图可以知道二分图的都是偶数圈；所以只要先把联通分量求出来然后判断是否是二分图就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

bool A[maxn][maxn];
struct Edge{
    int u,v;
};
///割顶 bccno 无意义
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cut;
vector<int>G[maxn],bcc[maxn];
stack<Edge>S;
int dfs(int u,int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v =G[u][i];
        Edge e = (Edge){u,v};
        if(!pre[v]){ ///没有访问过
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu=min(lowu, lowv);                ///用后代更新
            if(lowv >= pre[u]){
                iscut[u]=true;
                bcc_cut++;bcc[bcc_cut].clear();   ///注意 bcc从1开始
                for(;;){
                    Edge x=S.top();S.pop();
                    if(bccno[x.u] != bcc_cut){bcc[bcc_cut].push_back(x.u);bccno[x.u]=bcc_cut;}
                    if(bccno[x.v] != bcc_cut){bcc[bcc_cut].push_back(x.v);bccno[x.v]=bcc_cut;}
                    if(x.u==u&&x.v==v)break;
                }
            }
        }
        else if(pre[v] < pre[u] && v !=fa){
            S.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}
void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cut = 0;
    for(int i = 0; i < n;i++)
        if(!pre[i])dfs(i,-1);
}

int odd[maxn], color[maxn];
bool bipartite(int u,int b){
    for(int i = 0;i < G[u].size(); i++){
        int v =G[u][i]; if(bccno[v] != b) continue;
        if(color[v] == color[u])return false;
        if(!color[v]){
            color[v] = 3 - color[u];
            if(!bipartite(v,b))return false;
        }
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int kase=0,n,m;
    while(cin>>n>>m&&n){
        for(int i=0;i<n;i++) G[i].clear();

        memset(A,0,sizeof(A));
        for(int i=0;i<m;i++){
            int u,v;
            cin>>u>>v;
            u--;v--;
            A[u][v]=A[v][u]=1;
        }
        for(int u=0;u<n;u++){
            for(int v=u+1;v<n;v++){
                if(!A[u][v]){
                    G[u].push_back(v);
                    G[v].push_back(u);
                }
            }
        }

        find_bcc(n);

        memset(odd, 0, sizeof(odd));
        for(int i = 1; i <= bcc_cut; i++){
            memset(color, 0, sizeof(color));
            for(int j = 0;j < bcc[i].size(); j++) bccno[bcc[i][j]]=i;

            int u=bcc[i][0];
            color[u]=1;
            if(!bipartite(u,i))
                for(int j = 0;j < bcc[i].size(); j++)odd[bcc[i][j]]=1;
        }
        int ans=n;
        for(int i = 0; i < n; i++)if(odd[i])ans--;
        cout<<ans<<endl;

    }
    return 0;
}