传送门

迷宫中不能有回路,还要连通

如果最后集合数是一个那就是连通,否则不联通

要合并的两个顶点在相同集合内,表示出现了回路

输入时注意一下

 #include<bits/stdc++.h>
using namespace std;
int f[];
int getf(int v)
{
if(f[v]==v)return v;
else
{
f[v]=getf(f[v]);
return f[v];
}
}
void merge(int v,int u)
{
int t1,t2;
t1=getf(v);
t2=getf(u);
if(t1!=t2)
{
f[t2]=t1; }
return;
}
void init()
{
for(int i=; i<; i++)
{
f[i]=i;
}
}
int data[];
int main()
{
int x,y,num=,maxx=-,ans=,flag=;
memset(data,,sizeof(data));
init();
while(scanf("%d %d",&x,&y))
{
if(x==-&&y==-)break;
if(x!=&&y!=)
{
if(getf(x)==getf(y))flag=;
data[x]=x;
data[y]=y;
merge(x,y);
//int temp=x>y?x:y;
// maxx=maxx>temp?maxx:temp;
}
if(x==&&y==)
{
for(int i=; i<=; i++)
{
if(data[i])
{
if(getf(i)==i)ans++;
}
}
if(flag||ans>)
{
printf("No\n");
}
else
{
printf("Yes\n");
}
num=,maxx=-,ans=,flag=;
memset(data,,sizeof(data));
init();
}
}
return ;
}

最新文章

  1. jQuery 2.0.3 源码分析 Deferrred概念
  2. linux 可用内存查看
  3. R之pryr
  4. ArcGIS10的GDB文件解析(初步)
  5. mybatis 与 ehcache 整合[转]
  6. Some good questions
  7. apache基本配置
  8. 转:创建编码的WebTest
  9. 复杂JSON反序列化为类对象
  10. ImageMagick命令行工具
  11. js_js流程控制
  12. chrony配置的和相关命令
  13. FakeGame 集成总结
  14. JavaScript使用jsonp实现跨域
  15. 查AIX 版本和系统参数
  16. Android四大组件之一 -- Service详解
  17. Spring cloud consul 相关前提知识
  18. Mac SpotLight无法搜索
  19. 第10次Scrum会议(10/22)【欢迎来怼】
  20. jni里找不到刚添加的C++函数

热门文章

  1. JS DateTime 格式化
  2. ubuntu 12.04 64位 安装wps
  3. KVOController原理解析
  4. saltstack之编写自定义模块
  5. 初识Qt图片显示、平移及旋转
  6. c++——静态成员变量成员函数
  7. 【转】如何在VMware上安装macOS Sierra 10.12
  8. 【星云测试】Devops微服务架构下具有代码级穿透能力的精准测试
  9. TCP\UDP客户—服务器程序设计基本框架流程图
  10. ios开发UI篇--UILabel