python/TangDou/JiShuanKe/2023-03-16/T3669_1.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, k;
int x[N], y[N];

struct Node {
    int to, id; // id:哪个房间，to:另一只猫猫的号码
};

vector<Node> g[N];
vector<int> S;
bool st[N];

// void getnodes(int u) {
//     st[u] = 1;
//     S.push_back(u);
//     for (auto e : g[u]) {
//         int v = e.to;
//         if (!st[v]) getnodes(v);
//     }
// }

vector<int> C;
int fa[N], pre[N], res[N];
bool fi;

void findcycle(int u) {
    st[u] = 1;            // u号小猫已经找过房间了
    for (auto e : g[u]) { // 遍历u号小猫的每个可用房间
        int v = e.to, i = e.id;
        if (i == pre[u]) continue; // 不走回头路
        
        if (!st[v]) {              // 进入搜索
            fa[v] = u, pre[v] = i, findcycle(v);
            continue;
        }
        
        if (fi) continue;
        int q = u;
        while (q != v) {
            C.push_back(q), res[pre[q]] = (x[pre[q]] == q ? 2 : 1);
            q = fa[q];
        }
        res[i] = (x[i] == u ? 1 : 2);
        fi = 1;
        C.push_back(v);
    }
}

bool chk(int m) {
    // 多次二分，清空现场
    for (int i = 1; i <= n; i++) g[i].clear();
    memset(st, 0, sizeof(st)), memset(pre, 0, sizeof(pre)), memset(fa, 0, sizeof(fa));

    // 前m个房间
    for (int i = 1; i <= m; i++) {
        int u = x[i], v = y[i];
        // 无向图建图
        g[u].push_back({v, i}); // u这只猫猫，可以使用i这个房间，另外一个可以使用i房间的猫猫是v号
        g[v].push_back({u, i}); // v这只猫猫，可以使用i这个房间，另外一个可以使用i房间的猫猫是u号
    }

    for (int i = 1; i <= n; i++) { // 每只猫
        if (st[i]) continue;       // 如果访问过，就下一个
        fi = 0, C.clear();         // fi：i号小猫在哪个房间里？
        findcycle(i);              // 为i号小猫找房间
        if (!fi) return 0;         // 如果没有找到合适的房间，那么就表示当前的m太小的，需要扩大
    }
    return 1; // 检查通过，返回OK
}

void dfs(int u) {
    st[u] = 1;
    for (auto e : g[u]) {
        int v = e.to, i = e.id;
        if (st[v] || res[i] != 0) continue;
        res[i] = (x[i] == v ? 1 : 2);
        dfs(v);
    }
}

// void getans(int m) {
//     for (int i = 1; i <= n; i++) g[i].clear();
//     memset(st, 0, sizeof(st)), memset(pre, 0, sizeof(pre));
//     memset(fa, 0, sizeof(fa)), memset(res, 0, sizeof(res));

//     for (int i = 1; i <= m; i++) {
//         int u = x[i], v = y[i];
//         g[u].push_back({v, i}), g[v].push_back({u, i});
//     }

//     for (int i = 1; i <= n; i++) {
//         if (st[i]) continue;
//         S.clear();
//         getnodes(i);
//         fi = 0;
//         for (int p : S) st[p] = 0;
//         C.clear();
//         findcycle(i);
//         for (int p : S) st[p] = 0;
//         for (int p : C) st[p] = 1;
//         for (int p : C) dfs(p);
//         for (int p : S) st[p] = 1;
//     }

//     for (int i = 1; i <= m; i++) cout << res[i] << " ";
//     puts("");
// }

int main() {
    freopen("cats.in", "r", stdin);
    // freopen("cats.out", "w", stdout);

    cin >> n >> k;                            // n只小猫，k个房间
    for (int i = 1; i <= k; i++) cin >> x[i]; // k个房间，可以容纳x[i]的猫猫
    for (int i = 1; i <= k; i++) cin >> y[i]; // k个房间，可以容纳y[i]的猫猫

    int L = 1, R = k, ans = L; // 二分答案
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (chk(mid)) // 如果每个猫猫都可以有房间，那么检查通过,说明房间的数量还是很宽松的
            R = mid - 1, ans = mid;
        else
            L = mid + 1;
    }

    // 输出数量
    cout << ans << endl;

    // 输出方案
    // getans(ans);

    return 0;
}