877
並查集算法
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int MAX_NUM = 100;
string name[MAX_NUM];
int group[MAX_NUM];
int rank[MAX_NUM];
void MakeSet()
{
for (int i = 0; i < MAX_NUM; ++i)
{
group[i] = i;
rank[i] = 0;
}
}
int FindGroup(int i)
{
if (group[i] == i)
{
return group[i];
}
group[i] = FindGroup(group[i]);
}
int MyFoundGroup(int i)
{
return group[i];
}
void Union(int i, int j)
{
int g1 = FindGroup(group[i]);
int g2 = FindGroup(group[j]);
if (rank[g1] > rank[g2])
{
group[j] = g1;
}
else
{
group[i] = g2;
if (rank[g1] == rank[g2])
{
rank[g2]++;
}
}
}
bool JudgeGroup(string name1, string name2)
{
int index1 = -1;
int index2 = -1;
for (int i = 0; i < MAX_NUM; ++i)
{
if (name1 == name[i])
{
index1 = i;
break;
}
}
for (int i = 0; i < MAX_NUM; ++i)
{
if (name2 == name[i])
{
index2 = i;
break;
}
}
return MyFoundGroup(group[index1]) == MyFoundGroup(group[index2]);
}
int main()
{
name[0]="小明";
name[1]="小王";
name[2]="小軍";
name[3]="小麗";
name[4]="小李";
MakeSet();
Union(0,1);
Union(2,1);
Union(3,4);
string name1,name2;
cin >> name1 >> name2;
if(JudgeGroup(name1,name2))
{
cout << name1 << " 和 " << name2 << "是隊友." << endl;
}
else
{
cout << name1 << " 和 " << name2 << "不是隊友" << endl;
}
system("pause");
return 0;
}
最後更新：2017-04-03 15:21:51