Peienwu's Blog

Hello world

0%

[題解]APCS真假子圖

發表於 分類於 Valine：
文章字數： 4.5k 所需閱讀時間 ≈ 4 分鐘

P4 真假子圖

題目連結

二分搜尋+DFS作法

題解

一開始看到這題，應該很難通靈出二分搜這個作法（我覺得光把題目看懂就有點難度了）。這題有一個條件要特別注意：

保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合

這一題每一個觀察員並可看成不是獨立的（假如一個觀察員不產生矛盾，則他回傳的那一些邊都會被沿用），所以題目 $p$ 筆詢問可以聯集一起處理。

將情報員當成點，合作關係當成邊，那麼合法的圖就會有兩個點集，點集中的點互不相鄰，也就是二分圖。

二分搜第一個使得圖變得不二分的人，把它消失，最多重複3次就做完了。

為什麼可以二分搜？
二分搜是用來找一串01字串的分界點，並且必須具有單調性才能二分搜。這一題之所以會有單調性是因為，當我查詢觀察員$P_i$的回傳資料是否正確時，會將前面 $1$ 到 $i-1$ 的觀察員回傳的所有邊納入考慮。

假設有一個觀察員 $P_j(1\le j < i)$ 回傳的資料是錯誤的，這些邊會導致整張圖變成非二分圖，對於 $j$ 後面的所有點來說，都是非二分圖。這樣就有了以 $j$ 為分界點的單調性，即可二分搜。

二分圖判斷可以用 DFS 做，DFS 的時候把每個點塗上顏色，如果相鄰的點跟自己顏色一樣就表示這不是一張二分圖。

時間複雜度

$O((n + m + pk)\log p)$

AC程式碼

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
#include <bits/stdc++.h>
#define pb push_back
#define mid (l + r) / 2
using namespace std;
struct e{
    int u, v;
};
int n;
array<bool, 10004> WA;          //不可行的觀察員編號
array<int, 20004> vis;          //DFS是否走訪、二分圖顏色
array<vector<e>, 10004> E;      //每一個觀察員的回傳邊
array<vector<int>, 20004> G;    //存進行DFS的圖

bool dfs(int u, int t){         //用DFS塗色、判斷二分圖
    if(vis[u]) return 1;
    bool ans = 1;
    vis[u] = t;
    for(int v : G[u]){
        if(vis[v] == t) return 0;
        ans &= dfs(v, 3 - t);
    }
    return ans;
}

bool check(int p){               //檢查第p個觀察員回傳是否正確
    bool ans = 1;
    for(int i = 0; i < n; i++){
        G[i].clear();
        vis[i] = 0;
    }
    for(int i = 0; i <= p; i++){
        for(auto [u, v] : E[i]){ //將觀察員的邊推入G
            G[u].pb(v);
            G[v].pb(u);
        }
    }
    for(int i = 0; i < n; i++){
        ans &= dfs(i, 1);        //將每一個連通塊
    }
    return ans;
}
void BS(int l, int r){           //二分搜觀察員
    if(check(r)) return;         //當邊的連集不會讓圖有問題，則回傳
    while(l != r){
        if(check(mid)) l = mid + 1;
        else r = mid;
    }
    WA[l] = 1;
    E[l].clear();                //剔除一錯誤觀察員
}
signed main(){
    int m, p, k, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        E[0].pb({a, b});
    }
    cin >> p >> k;
    for(int i = 1; i <= p; i++){
        for(int j = 0; j < k; j++){
            cin >> a >> b;
            E[i].pb({a, b});
        }
    }
    for(int i = 0; i < 3; i++){     //至多三個觀察員
        BS(0, p);
    }
    for(int i = 1; i <= p; i++){
        if(WA[i]) cout << i << "\n";
    }
    return 0;
}

BY thanksone

DSU作法

Idea From Kennyfs

題解

這一題的題目限制有說最多3個錯誤的情報員，因此我們可以用上面二分搜的方式做三次找到答案。如果題目不限制錯誤調查員的數量，也就是用二分搜時間會超時，但是用DSU可以在線性時間內完成！

DSU的目的在處理集合問題，根據下面這個關鍵條件：

保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合

我們只要對每一筆詢問看會不會與組長手中的pair矛盾即可。如果每一次都做DFS，會發現時間複雜度是 $O(pn)$，必然超時。

DSU的想法是，我們將組長手中的圖中上每一個連通塊都分別塗上兩種顏色（必為二分圖，因此將兩邊各塗上不同顏色）。接著，把每個顏色當作初始的並查集中的集合，將每一筆觀察員回傳的邊的兩端指向的集合合併起來，過程中如果發生邊的兩端同屬一個集合，表示這是一個錯誤的觀察員。做完每一個觀察員之後，把所有變更過的還原成初始狀態（組長手中的圖）即可。

舉例

8 5
0 2 1 3 1 2 4 6 5 6
1 2
1 4 0 6

整個過程就是下面這張GIF：

步驟：

  1. 利用DFS為組長手中的圖上色，每一個連通塊兩色（以編號1,2,3…）
  2. 將每一個顏色當作並查集元素
  3. 觀察員輸入的邊兩端 $(u,v)$非同色，表示不發生矛盾，則將u所在集合與v所在集合的對方（連通塊兩色的另一色）合併
  4. 重複 步驟3 共k次，如果發生$(u,v)$為同一色，則觀察員錯誤。

時間複雜度

$O(n + pk\alpha)$

AC程式碼

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
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define int long long
#define N 20005
#define M 10005
using namespace std;
int n,m,p,k;
int color[N],boss[N],num[N];
bool WA[M],f;
int other(int s){return (s%2)?s+1:s-1;} //other為同一連通塊另外一種顏色
vector<int> edge[N],change;

void init(){                            //初始化
    memset(color,0,sizeof(color));
    memset(WA,0,sizeof(WA));
}
void dfs(int id,int col){           //對所有點上色
    color[id] = col;
    for(auto i:edge[id]){
        if(!color[i])dfs(i,other(col));
    }
}
int find_boss(int id){              //尋找祖先、及路徑壓縮
    if(boss[id] == id)return id;
    change.push_back(id);
    return boss[id] = find_boss(boss[id]);
}

signed main(){
    IOS;
    init();
    cin>>n>>m;
    while(m--){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    int now = 1;
    for(int i=0;i<n;i++){           //對所有點上色
        if(!color[i]){
            dfs(i,now);now += 2;
        }
    }
    for(int i=1;i<=now;i++){boss[i] = i;num[i] = 1;}
    cin>>p>>k;
    for(int i=1;i<=p;i++){
        change.clear();                                  //儲存待更改的點集f = 0;
        for(int j=0;j<k;j++){
            int x,y;cin>>x>>y;
            if(f)continue;
            x = color[x],y = color[y];                   //尋找邊兩端點的顏色所處的集合
            int bx =  find_boss(x),by = find_boss(y);
            int ox = find_boss(other(y)),oy = find_boss(other(x));
            if(bx == by){WA[i] = 1;f = 1;continue;}     //位於同一集合，此觀察員是錯的
            //以下是啟發式合併（小的集合並到大的集合）
            if(num[bx] < num[ox]){
                boss[bx] = ox;num[ox] += num[bx];
                change.push_back(bx);
            }
            else{
                boss[ox] = bx;num[bx] += num[ox];
                change.push_back(ox);
            }
            if(num[by] < num[oy]){
                boss[by] = oy;num[oy] += num[by];
                change.push_back(by);
            }
            else{
                boss[oy] = by;num[by] += num[oy];
                change.push_back(oy);
            }
        }
        for(auto i : change){boss[i] = i;num[i] = 1;}   //觀察員的邊結束，看完後復原
    }
    for(int i=1;i<=p;i++)if(WA[i])cout<<i<<endl;        //輸出最後錯誤觀察員答案
}

BY peienwu