题目

链接：https://ac.nowcoder.com/acm/contest/28886/1021
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

DongDong每年过春节都要回到老家探亲，然而DongDong记性并不好，没法想起谁是谁的亲戚（定义:若A和B是亲戚，B和C是亲戚，那么A和C也是亲戚），她只好求助于会编程的你了。

输入描述:
第一行给定n,m表示有n个人，m次操作

第二行给出n个字符串，表示n个人的名字分别是什么(如果出现多个人名字相同，则视为同一个人)（保证姓名是小写字符串）

接下来m行，每行输入一个数opt,两个字符串x,y

当opt=1时，表示x,y是亲戚

当opt=2时，表示询问x,y是否是亲戚，若是输出1，不是输出0

数据范围:1<=n,m<=20000，名字字符长度小等于10
输出描述:
对于每个2操作给予回答
示例1

输入
4 4

chen lin yi cheng

2 chen lin

1 chen lin

1 yi lin

2 yi lin
输出
0

1

代码

#include <cstdio>

#include <map>

#include <string>

#include <iostream>

using namespace std;

int r[20010];

int fa[20010];

map<string, int>mp;

int find(int x)

{

	return x == fa[x] ? x : fa[x] = find(fa[x]);

}

inline void mer(int x, int y)//注意:必须要进行判断是不是一个集合

{

	int xg = find(x);

	int yg = find(y);

	if (xg == yg)

		return;

	if (r[xg] > r[yg])

	{

		fa[yg] = fa[xg];

	}

	else if (r[xg] < r[yg])

	{

		fa[xg] = fa[yg];

	}

	else

	{

		fa[yg] = fa[xg];

		r[xg]++;

	}

}

int main()

{

	int n, m;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++)

	{

		string s;

		cin >> s;

		mp[s] = i;//虽然名字相同认为一个人,map本来就是单一容器

		fa[i] = i;

	}

	for (int i = 0; i < m; i++)

	{

		int  op;

		string s1;

		string s2;

		scanf("%d", &op);

		cin >> s1 >> s2;

		switch (op)

		{

		case 1:

			mer(mp[s1], mp[s2]);

			break;

		case 2:

			if (find(mp[s1]) == find(mp[s2]))

			{

				printf("1\n");

			}

			else

				printf("0\n");

			break;

		}

	}

	return 0;

}

巴特西

DongDong认亲戚来源：牛客网

题目

题目描述

输入描述:

输出描述:

输入

输出

代码

最新文章

热门文章

巴特西

DongDong认亲戚 来源：牛客网

题目

题目描述

输入描述:

输出描述:

输入

输出

代码

最新文章

热门文章

DongDong认亲戚来源：牛客网