hdu1272小希的迷宫(并查集判断回路和是否连通)
2024-10-10 03:52:28
迷宫中不能有回路,还要连通
如果最后集合数是一个那就是连通,否则不联通
要合并的两个顶点在相同集合内,表示出现了回路
输入时注意一下
#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 ;
}
最新文章
- jQuery 2.0.3 源码分析 Deferrred概念
- linux 可用内存查看
- R之pryr
- ArcGIS10的GDB文件解析(初步)
- mybatis 与 ehcache 整合[转]
- Some good questions
- apache基本配置
- 转:创建编码的WebTest
- 复杂JSON反序列化为类对象
- ImageMagick命令行工具
- js_js流程控制
- chrony配置的和相关命令
- FakeGame 集成总结
- JavaScript使用jsonp实现跨域
- 查AIX 版本和系统参数
- Android四大组件之一 -- Service详解
- Spring cloud consul 相关前提知识
- Mac SpotLight无法搜索
- 第10次Scrum会议(10/22)【欢迎来怼】
- jni里找不到刚添加的C++函数