luogu P3144 [USACO16OPEN]關(guān)閉農(nóng)場Closing the Farm_Silver解題報告

題目描述

Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime.

The farm consists of NN barns connected with MM bidirectional paths between some pairs of barns (1 \leq N, M \leq 30001≤N,M≤3000). To shut the farm down, FJ plans to close one barn at a time. When a barn closes, all paths adjacent to that barn also close, and can no longer be used.

FJ is interested in knowing at each point in time (initially, and after each closing) whether his farm is "fully connected" -- meaning that it is possible to travel from any open barn to any other open barn along an appropriate series of paths. Since FJ's farm is initially in somewhat in a state of disrepair, it may not even start out fully connected.

FJ和他的奶牛們正在計劃離開小鎮(zhèn)做一次長的旅行，同時FJ想臨時地關(guān)掉他的農(nóng)場以節(jié)省一些金錢。

這個農(nóng)場一共有被用M條雙向道路連接的N個谷倉(1<=N,M<=3000)。為了關(guān)閉整個農(nóng)場，F(xiàn)J 計劃每一次關(guān)閉掉一個谷倉。當一個谷倉被關(guān)閉了，所有的連接到這個谷倉的道路都會被關(guān)閉，而且再也不能夠被使用。

FJ現(xiàn)在正感興趣于知道在每一個時間（這里的“時間”指在每一次關(guān)閉谷倉之前的時間）時他的農(nóng)場是否是“全連通的”——也就是說從任意的一個開著的谷倉開始，能夠到達另外的一個谷倉。注意自從某一個時間之后，可能整個農(nóng)場都開始不會是“全連通的”。

輸入輸出格式

輸入格式：

The first line of input contains NN and MM. The next MM lines each describe a

path in terms of the pair of barns it connects (barns are conveniently numbered

1 \ldots N1…N). The final NN lines give a permutation of 1 \ldots N1…N

describing the order in which the barns will be closed.

輸出格式：

The output consists of NN lines, each containing "YES" or "NO". The first line

indicates whether the initial farm is fully connected, and line i+1i+1 indicates

whether the farm is fully connected after the iith closing.

輸入輸出樣例

4 3
1 2
2 3
3 4
3
4
1
2

YES
NO
YES
YES

這道題有一個判連通性過程，馬上應該想到并查集這種好東西，但是我們從一個集合去拆肯定會很麻煩的，時間上也無法被允許，那么我們正難則反，既然正著推比較麻煩，那我們?yōu)槭裁床话堰@個關(guān)閉的過程倒過來想象成打開呢，剛開始都是關(guān)閉狀態(tài)，然后一個個打開，最后倒著輸出即可，不多說了上代碼

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,a[3005][3005],p[3005],check[3005],fa[3005],ans[3005];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=1;
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
        scanf("%d",&p[i]);
    }
    for(int i=n;i>=1;i--){
        check[p[i]]=1;
        for(int j=1;j<=n;j++)
            if(check[j]&&a[p[i]][j]){
                //if(i==2) printf("%d %d\n",p[i],j);
                fa[find(p[i])]=find(j);
            }
        int cnt=0;
        for(int j=1;j<=n;j++)
            if(check[j]&&fa[j]==j) cnt++;
        if(cnt>1) ans[i]=1;
    }
    for(int i=1;i<=n;i++)
        if(ans[i]) printf("NO\n");
        else printf("YES\n");
    return 0;
}