题解 P5429 【[USACO19OPEN]Fence Planning S】

· · 题解

麻烦管理员好好看看我的题解，我的解法哪里重复了？？？

看到前面的大佬都用的是并查集，我就发一篇

DFS的题解吧

基本的思路已经很清楚，基础的图论题目，先用链接表建图，然后对着图进行遍历。至于如何遍历，这道题需要找到每一个联通快，所以可以开一个vis数组标记一下这个点有没有遍历过，然后从一号节点开始，只要发现这个节点没有被标记过，就拿这个点开始把整个联通快都遍历，然后不断修正这个矩形的上方下方、左边右边。这个可以通过DFS/BFS来实现。这里放的是DFS方法。

这里就不详细说了，代码里都有注释。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,maxe=maxn<<1;
int U,D,L,R,ans=2147483647,n,m,son[maxe],nxt[maxe],lik[maxn],tot; bool vis[maxn];
inline int read(){  //快读 
    int ret=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret*f;
}
void add_e(int x,int y){son[++tot]=y,nxt[tot]=lik[x],lik[x]=tot;}
    /*这里是用链接表建边，不再多说*/
struct cow{int x,y;}a[maxn];
void DFS(int step){
    vis[step]=1;    //标记遍历过了 
    U=max(U,a[step].y),D=min(D,a[step].y);
    R=max(R,a[step].x),L=min(L,a[step].x);
        //这里的U,D,L,R分别指up,down,left,right,这里就是碰到一个节点就修正矩形 
    for(int j=lik[step];j;j=nxt[j]) if(!vis[son[j]]) DFS(son[j]);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=(cow){read(),read()};
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        add_e(x,y),add_e(y,x);
    }
    for(int i=1;i<=n;i++) if(!vis[i]){  //找到没有遍历到的了 
        U=D=a[i].y,L=R=a[i].x; //给矩形赋最初的值 
        DFS(i);
        ans=min(ans,((U-D)+(R-L))<<1);      //修正答案， ((U-D)+(R-L))<<1就是周长 
    }
    printf("%d\n",ans);
    return 0;
}

然而，你们会有疑惑这个代码的时间复杂度吗？看了我的代码，看到了一个for循环里面还有一个DFS，你们会不会认为这是n^2的？哈哈，其实不是的。因为当你发现一个节点并遍历了以后，与它相关的节点就都不会再次遍历到了，所以时间复杂度其实是O(n)级别的。

完结撒花~