Vegetable and Road [并查集]

2019-11-06 06:23:19

字体：大中小

来源：转载

供稿：网友

公园终于建好了，市政府要求任意两个公园之间必须连通，即公园A到公园B至少有一条马路（并不是要求直接相连，可以通过其他公园间接相连）。

Vegetable接下来这个任务，并设计出了对应的修路方案，下面你需要判断Vegetable的方案是否可行。

注意：两个公园直接可以存在多条路。

输入有T组测试数据，每组测试数据有一组N(0

#include<cstdio>#include<cstring>#include<cmath>#include<stack>#include<queue>#include<algorithm>using namespace std;#define INF 0x3f3f3f3f#define ll long longint par[1005];bool vl[1005];int n;void init(){ for (int i = 1; i <= n; ++i){ par[i] = i; }}int find(int x){ int temp = x; if (x == par[x]) return x; return par[x] = find(par[x]);}void unit(int x,int y){ vl[x] = true; vl[y] = true; int tx = find(x); int ty = find(y); if (tx == ty) return ; par[ty] = tx; }int u,v;int main(){ int t; scanf("%d",&t); while (t--){ memset(vl,false,sizeof(vl)); int m; scanf("%d%d",&n,&m); init(); int ta; for (int i= 0; i < m; ++i){ scanf("%d%d",&u,&v); unit(u,v); } int flag = 1; for (int i = 1; i <= n; ++i){ for (int j = 1; j <= n; ++j){ if (find(i)!=find(j)) flag = 0; } } if (flag == 0) PRintf("No/n"); else printf("Yes/n"); } return 0;}

wa了好几次在判断是否有森林上这个题每个公园的坐标为1到n直接搜1到n 需要好好的整理一下并查集的知识点了

模板题都能卡= =

上一篇：opencv，图像处理，rgb转换为hsv空间

下一篇：Qtudp组播编程