自动搬运

查看原文

来自洛谷，原作者为

	Mkarry AFO

搬运于2025-08-24 22:10:39，当前版本为作者最后更新于2020-02-03 18:45:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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)$级别的。

完结撒花~