这种方法还有救吗
查看原帖
这种方法还有救吗
882092
zMinYu楼主2022/11/21 17:59
/*
map+并查集 
*/
#include<bits/stdc++.h>
using namespace std;
int x,y,g;
unordered_map<string,string>no_inone,inone;
string find_no(string x)
{
	if(no_inone[x]==x)
	return x;
	else 
	return no_inone[x]=find_no(no_inone[x]);
}
string find_in(string x)
{
	if(inone[x]==x)
	return x;
	else 
	return inone[x]=find_in(inone[x]);
}
void merge_no(string x,string y)
{
	string xx=find_no(x),yy=find_no(y);
	no_inone[xx]=yy;
} 
void merge_in(string x,string y)
{
	string xx=find_in(x),yy=find_in(y);
	inone[xx]=yy;
} 
int main()
{
	cin>>x;
	string name1,name2,name3;
	for(int i=1;i<=x;i++)
	{
		cin>>name1>>name2;
		merge_in(name1,name2);
	}
	cin>>y;
	for(int i=1;i<=y;i++)
	{
		cin>>name1>>name2;
		merge_no(name1,name2);
	}
	cin>>g;
	int ans=0;
	for(int i=1;i<=g;i++)
	{
		cin>>name1>>name2>>name3;
		for(auto x:inone)
		{
			if(name1==x.first)
			{
				if(name2!=x.second&&name3!=x.second) ans++;
			}
			if(name1==x.second)
			{
				if(name2!=x.first&&name3!=x.first) ans++;
			}
			if(name2==x.first)
			{
				if(name1!=x.second&&name3!=x.second) ans++;
			}
			if(name2==x.second)
			{
				if(name1!=x.first&&name3!=x.first) ans++;
			}
			if(name3==x.first)
			{
				if(name1!=x.second&&name2!=x.second) ans++;
			}
			if(name2==x.second)
			{
				if(name1!=x.first&&name2!=x.first) ans++;
			}
		}
		for(auto x:no_inone)
		{
			if(name1==x.first)
			{
				if(name2==x.second||name3==x.second) ans++;
			}
			if(name1==x.second)
			{
				if(name2==x.first||name3==x.first) ans++;
			}
			if(name2==x.first)
			{
				if(name1==x.second||name3==x.second) ans++;
			}
			if(name2==x.second)
			{
				if(name1==x.first||name3==x.first) ans++;
			}
			if(name3==x.first)
			{
				if(name1==x.second||name2==x.second) ans++;
			}
			if(name2==x.second)
			{
				if(name1==x.first||name2==x.first) ans++;
			}
		}
	}
	cout<<ans/2;//一百零九行,我真的服了呀 
	return 0;
}
2022/11/21 17:59
加载中...