zoj 3811 Untrusted Patrol(BFS+並查集)

zoj 3811 Untrusted Patrol(BFS+並查集)

題目鏈接：zoj 3811 Untrusted Patrol

題目大意：給定n，m，k，表示有n個倉庫，m條通道，k個傳感器，現在給定n個傳感器的位置和m條通道，現在要最這n個倉庫進行巡邏，要求一次進過給定具有傳感器的倉庫，每個倉庫經過的次數不限，單要求至少進過1次。

解題思路：首先判斷是否為聯通圖，不連通的話肯定到不了。其次判斷l是否等於k，如果不等於的話，說明至少有一個倉庫到不了，剩下的就是考慮進過倉庫的順序，因為起點不限，所以第一個倉庫的位置不會有問題，以第一個倉庫為起點，做BFS，碰到有傳感器的倉庫將傳感器關閉，並且將節點標記為1，表示說下一個位置可以直接到達該位置。然後考慮第二個位置，如果第二位置上的傳感器沒有關閉，則說明由第一個倉庫到不了第二個倉庫，否則重復操作，以第二個倉庫為起點，做BFS

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 100005;

bool flag;
int N, M, C, t[maxn], v[maxn], f[maxn];
vector g[maxn];

inline int getfar(int x) {
    return x == f[x] ? x : f[x] = getfar(f[x]);
}

void init () {
    scanf("%d%d%d", &N, &M, &C);
    int x, a, b, n = N;

    memset(t, 0, sizeof(t));
    memset(v, 0, sizeof(v));
    for (int i = 0; i <= N; i++) {
        f[i] = i;
        g[i].clear();
    }

    for (int i = 0; i < C; i++) {
        scanf("%d", &x);
        t[x] = 1;
    }

    for (int i = 0; i < M; i++) {
        scanf("%d%d", &a, &b);

        g[a].push_back(b);
        g[b].push_back(a);

        int p = getfar(a), q = getfar(b);
        if (p != q) {
            f[p] = q;
            n--;
        }
    }

    flag = (n == 1);
}

void bfs(int s) {
    queue que;
    t[s] = 0; v[s] = 1;
    que.push(s);

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int i = 0; i < g[u].size(); i++) {
            int k = g[u][i];

            if (v[k] || t[k]) {
                v[k] = 1;
                t[k] = 0;
                continue;
            }

            v[k] = 1;
            que.push(k);
        }
    }
}

bool judge () {
    int n, x;
    scanf("%d", &n);

    if (n < C)
        flag = false;

    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (flag == false || (t[x] && i)) {
            flag = false;
            continue;
        }
        bfs(x);
    }
    return flag;
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        init();
        printf("%s\n", judge() ? "Yes" : "No");
    }
    return 0;
}