ACdream区域赛指导赛之手速赛系列(4)

本文主要是介绍ACdream区域赛指导赛之手速赛系列(4)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开题目链接

#include <iostream>
#include <map>
#include <cstdio>
#include <string>
using namespace std;
int a[501];
//题意是能不能把一组两个人分到两个不同的正营里面,关键利用map映射
void init()
{
for(int i = 0; i <= 200; i++)
{
a[i] = i;
}
}
int Find(int x)
{
while(x != a[x])
x= a[x];
return x;
}
void Union(int x,int y)
{
int fx = Find(x);
int fy = Find(y);
if(fx != fy)
{
a[fx] = fy;
}
}
int main()
{
int t;
cin >> t;
for(int j = 1; j <= t; j++)
{
init();
map<string,int> ma;
int m,cnt = 1;
cin >> m;
bool flag = true;
for(int i = 0; i < m ; i++)
{
string s1,s2;
cin >> s1 >> s2;
if(!ma[s1]) ma[s1] = cnt++;
if(!ma[s2]) ma[s2] = cnt++;
if(Find(ma[s1]) == Find(ma[s2]) )
{
flag = false;
}
//核心代码
/*
101A集合表示和x同类的，B集合表示和x异类（x+200）。现在x和y异类，并且x和x+200异类，说明y和x+200同类；
同时x和y异类，y+200和y异类， 说明x和y+200同类。我们需要把所有同类的放到一个集合里，避免遗漏的情况。                          */
Union(ma[s1],ma[s2] + 101); 
Union(ma[s2],ma[s1] + 101);
}
printf("Case #%d: %s\n",j,flag ? "Yes":"No");
}
return 0;
}

 

这篇关于ACdream区域赛指导赛之手速赛系列(4)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---