首页 > 其他分享 >EOJ 小强的烦恼

EOJ 小强的烦恼

时间:2023-11-10 13:23:20浏览次数:32  
标签:int EOJ 烦恼 fa edge 小强 xy find

EOJ 1837小强的烦恼

思路

使用带权并查集处理这个题目,根据敌人的敌人是朋友的原则,xy的边权为偶数,则xy是朋友,否则是敌人。如果xy不在同一个并查集里面,则暂时不确定。

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int fa[MAXN];
int edge[MAXN];
inline int find(int x)
{
	if(x == fa[x]) return x;
	int tf = fa[x];
	fa[x] = find(fa[x]);
	edge[x] = (edge[x] + edge[tf]) % 2;
	return fa[x];
}
inline void merge(int x, int y)
{
	if(x == y) return;
	edge[x] = edge[y] + 1;	
	x = find(x);
	y = find(y);
	fa[x] = y;
}
int n, m;
inline void sov()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		fa[i] = i;
	for(int i = 1; i <= n; ++i) 
		edge[i] = 0;
	while(m--)
	{
		char c;
		int x, y;
		cin >> c >> x >> y;
		if(c == 'A')
		{
			merge(x, y);
		}
		else if(c == 'Q')
		{
			int nx = find(x);
			int ny = find(y);
			if(nx != ny)
			{
				cout << "Not sure yet.\n";
			}
			else
			{
				int d = edge[x] + edge[y];
//				cerr << nx << " " << edge[x] << " " << edge[y] << endl;
				if(d % 2 == 0)
				{
					cout << "In the same gang.\n";	
				}
				else
				{
					cout << "In different gangs.\n";
				}	
			}
		} 
	}
}
int main()
{
	int t;
	cin >> t;
	while(t--) sov();
}

标签:int,EOJ,烦恼,fa,edge,小强,xy,find
From: https://www.cnblogs.com/Shiina-Rikka/p/17823875.html

相关文章

  • Python-geojson转shp 工具
    工具使用演示: ......
  • 2023年11月最新全国省市区县和乡镇街道行政区划矢量边界坐标经纬度地图数据 shp geojs
    发现个可以免费下载全国 geojson 数据的网站,推荐一下。支持全国、省级、市级、区/县级、街道/乡镇级以及各级的联动数据,支持导入矢量地图渲染框架中使用,例如:D3、Echarts等geojson数据下载地址:https://geojson.hxkj.vip该项目github地址:https://github.com/TangSY/echarts-m......
  • 2023年10月最新全国省市区县和乡镇街道行政区划矢量边界坐标经纬度地图数据 shp geojs
    发现个可以免费下载全国 geojson 数据的网站,推荐一下。支持全国、省级、市级、区/县级、街道/乡镇级以及各级的联动数据,支持导入矢量地图渲染框架中使用,例如:D3、Echarts等geojson数据下载地址:https://geojson.hxkj.vip该项目github地址:https://github.com/TangSY/echarts-m......
  • Python中生成GeoJSON数据
    要在Python中生成GeoJSON数据,可以使用GeoJSON库,例如geojson库或geopandas库。以下是使用这些库生成GeoJSON数据的简单示例:使用geojson库生成GeoJSON数据首先,确保已安装了geojson库,可以使用pip进行安装:pipinstallgeojson然后,可以按照以下方式生成GeoJSON数据:importgeojso......
  • 俞敏洪《一瓶黄河水》-不要让烦恼把快乐的部分污染了
    俞敏洪写过一篇文章:《一瓶黄河水》。某年,他去黄河旅行。因为心里装了不少工作上的烦心事,望着浑浊汹涌的黄河,他一时没了游玩的心情,竟想起了洪水和灾难。原本是出来散心的,现在变成了闹心。郁闷之中,他灌了一瓶子黄河水,坐在路边发起呆来。等他醒过神来,忽然发现瓶子里3/4变得非常清澈,剩......
  • RTMP视频服务器EasyDSS互联网视频直播点播平台如何基于FastDFS、ffmpeg、videojs实现
    互联网视频直播点播EasyDSS平台能实现视频流媒体的上传、转码、存储、录像、推流、拉流、直播等功能,在场景上,可以应用到互联网教育、在线课堂、游戏直播、视频点播、无人机等领域。 视频点播平台是指提供用户上传、存储和播放视频内容的在线平台。它可以让用户随时随地观看各......
  • wkt转换成geojson的代码
    安装及导入(在安装shapely之前一定要先安装geos)pipinstallgeospipinstallshapely下面是一个使用Python将WKT转换为GeoJSON的代码示例:importjsonfromshapely.wktimportloadswkt="POINT(1010)"shape=loads(wkt)geojson=json.dumps(shape.__geo_inter......
  • 一次搞定:借助Hutool封装代码快速解决webservice调用烦恼
    前言相信很多同行哪怕学了许多主流技术,但工作上依然免不了和传统企业打交道,而这样的企业往往还在用webservice做接口交互。本文是作者近两年和医疗行业的厂家打交道研究出来的一点调用webservice接口的心得,代码在生产环境也用了挺久了,专门捞出来作为一期干货分享给大家。......
  • excel的烦恼
    Smiling&Weeping----他未对我好半分,偏巧这感情疯长似野草 题目链接:https://www.matiji.net思路:与新三进制2思路相似,转化为纯26进制,然后往前遍历创造出符合题目要求的Talkischeap,showmethecode 1#include<bits/stdc++.......
  • 程序代做服务:解放您的编程烦恼
    导言:在现代技术驱动的社会中,编程已经成为了解决问题和创新的重要手段。然而,不是每个人都拥有编程的技能和时间来完成复杂的编程任务。在这样的情况下,程序代做服务应运而生,为那些需要技术支持的个人和企业提供了便利。什么是程序代做服务?程序代做服务是一种服务模式,通过该模式,您......