@Alpacadh
2019-01-30T09:10:34.000000Z
字数 3373
阅读 747
ACM
首先给出一些坏电脑的坐标(点),然后给出两种操作:
、修复编号为的电脑;
、 查询编号为 、 电脑是否有联系。
关于两台电脑的联系:
、如果编号为电脑已被修复,编号为的电脑也被修复,且它们的距离小于D;
、若编号为的电脑与编号为的电脑有联系,编号为的电脑与编号为的电脑有联系,则编号为的电脑与编号为 的有联系(传递性);
//#include<bits/stdc++.h>//因为POJ不支持万能表头 所以只能注释掉自己打所需要的函数库
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+5;
const double eps=1e-4;
int fa[N];
void init(int n)//初始化fa数组
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int findd(int x)
{
if(x==fa[x])
return x;
else
{
return fa[x]=findd(fa[x]);
}
}
bool Union(int x,int y)
{
int fx=findd(x),fy=findd(y);
if(fx==fy)
return false;
else
{
fa[fx]=fy;
return true;
}
}
struct point
{
int x,y;
}p[N];
int k;
int check(int a,int b)
{
return hypot(p[a].x-p[b].x,p[a].y-p[b].y)<=k;//hypot(a,b)返回的是以a,b为边的三角形的腰长,所以根据勾股定理这里可以用来算两点距离,但注意返回的是类型double。
}
int vis[N];
int main()
{
int n;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
char s[2];
init(n);
while(~scanf("%s",s))
{
int a,b;
if(s[0]=='O')
{
scanf("%d",&a);
vis[a]=1;
for(int i=1;i<=n;i++)
{
if(vis[i]==1&&a!=i&&check(a,i))//判断是否被修复,该点不能是自身,与它相距小于D
{
Union(a,i);
}
}
}
else
{
scanf("%d%d",&a,&b);
if(findd(a)==findd(b))
printf("SUCCESS\n");
else
printf("FAIL\n");
}
}
return 0;
}
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e4+5;
const double eps=1e-4;
int fa[N];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int findd(int x)
{
if(x==fa[x])
return x;
else
{
return fa[x]=findd(fa[x]);
}
}
bool Union(int x,int y)
{
int fx=findd(x),fy=findd(y);
if(fx==fy)
return false;
else
{
fa[fx]=fy;
return true;
}
}
int main()
{
int cas=1;
int n,m;
while(~scanf("%d%d",&n,&m))//注意多组输入
{
if(n==0&&m==0)//终止输入的条件
break;
init(n);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
}
int ans=0;
for(int i=0;i<n;i++)
{
if(fa[i]==i)//判断他当前信仰的宗教是否与原来的相同
ans++;
}
printf("Case %d: %d\n",cas++,ans);//注意输出不要漏掉Case
}
return 0;
}
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e4+5;
const double eps=1e-4;
int fa[N];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int findd(int x)
{
if(x==fa[x])
return x;
else
{
return fa[x]=findd(fa[x]);
}
}
bool Union(int x,int y)
{
int fx=findd(x),fy=findd(y);
if(fx==fy)
return false;
else
{
fa[fx]=fy;
return true;
}
}
int main()
{
int cas=1;
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
init(2*n);//注意因为有矛盾面的存在,所以fa数组要舒适化两倍。
int vis=0;//标记
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b+n);//与对面矛盾面结合
Union(b,a+n);
if(findd(a)==findd(a+n)||findd(b)==findd(b+n))//判断是否与自己的矛盾面在相同集合
{
vis=1;
}
}
printf("Scenario #%d:\n",cas++);
if(vis==1)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
printf("\n");
}
return 0;
}