华为机试-朋友圈个数C++解法

给定一组朋友关系，统计一下该朋友关系网中的朋友圈个数。

朋友圈的定义:一个朋友圈至少由3个朋友组成，且要求同一个朋友圈中的任意两个人都具有直接的朋友关系。
输入描述
输入一个朋友关系列表，如 Fiends =A.B],[A.C],IB,DI，其中的每一个元素 Friendsi表示 Friends[i][0)和 Friends [i][1] 是朋友关系 先输入一个数字 N 代表关系的总数，后面每条关系一行，两个成员以逗号分隔
输出描述
输出一个整数，表示整个关系网中朋友圈的个数
补充
1：Friends.length>=1，Friends.length<= 10^3
2：输入的总朋友个数<= 100
3：输入保证 Friend[i][0]和 Friend[i][1]一定不一样，且同一关系不会反向输入，即不会同时输入[A,B] 和 [B,A]。

4：不考虑子朋友圈，即当发现 [A,B,C,D]组成一个朋友圈时，[A,B,C]、[A,B,D]等子朋友圈不单独计数

示例1：

输入：

3
A,B
A,C
B,D

输出：

0

示例2：

输入：

7
A,B
A,C
B,C
A,D
D,E
B,D
A,E


输出：

3

示例3：

输入：

6
A,B
A,C
B,C
A,D
B,D
D,C

输出：

1
————————————————
版权声明：本文为CSDN博主「MISAYAONE」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/misayaaaaa/article/details/155455278

//bronKerbosch算法是最优解，但是对于现在的我来说好难啊！如果考试考到了还是老老实实邻接矩阵+暴力算法吧，起码简单一些的用例应该是能通过的
#牛客AI配图神器#
#include <iostream>
#include <unordered_map>
#include <string>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;

//定义全局变量
bool isFriend[100][100] = { false };//记录谁和谁是朋友
int totalPeople;
vector<int> maxCircle;

//P-还可以考虑加入到朋友圈的人
//X-已经排除，不考虑的人
void bronKerbosch(int R, int P, int X) {
if (P == 0 && X == 0) {
if (std::bitset<32>(R).count() >= 3) {
maxCircle.push_back(R);
}
return;
}
int pivot = 0;//枢顶点ID
if (P != 0) {
//找到P中第一个人的id
for (int i = 0; i < totalPeople; i++) {
if (P & (1 << i)) {
pivot = i;
break;
}
}
}
//遍历P中所有不是枢轴朋友的人
for (int v = 0; v < totalPeople; v++) {
//检查P的第v位是否为1
if (P & (1 << v)) {
//if (!isFriend[pivot][v]) continue;
int newR = R | (1 << v);
int newP = 0;
for (int u = 0; u < totalPeople; u++) {
if ((P & (1 << u)) && isFriend[v][u]) {
newP |= (1 << u);
}
}
//计算新的X
int newX = 0;
for (int u = 0; u < totalPeople; u++) {
if ((X & (1 << u)) && isFriend[v][u]) {
newX |= (1 << u);
}
}
//递归
bronKerbosch(newR, newP, newX);
P &= ~(1 << v);
X |= (1 << v);
}
}
}

int main() {
////声明变量名
intN;
cin >> N;
cin.ignore();

if (N <= 0) {
cout << 0 << endl;
return 0;
}

//把人名转换为数字编号
unordered_map<string, int> idMap;
vector<string> names;
int nextId = 0;

//读取所有朋友关系
for (int i = 0; i < N; i++) {
string line;
getline(cin, line);  // 读取整行

// 处理可能的空格
size_t commaPos = line.find(',');
if (commaPos == string::npos) {
// 没有逗号，格式错误
continue;
}

string a = line.substr(0, commaPos);
string b = line.substr(commaPos + 1);

// 去除首尾空格
a.erase(0, a.find_first_not_of(" \t"));
a.erase(a.find_last_not_of(" \t") + 1);
b.erase(0, b.find_first_not_of(" \t"));
b.erase(b.find_last_not_of(" \t") + 1);

// 给人分配id
if (!idMap.count(a)) {
idMap[a] = nextId++;
}
if (!idMap.count(b)) {
idMap[b] = nextId++;
}
int idA = idMap[a];
int idB = idMap[b];
//标记他们是朋友
isFriend[idA][idB] = true;
isFriend[idB][idA] = true;
}
totalPeople = nextId;

if (totalPeople < 3) {
cout << 0 << endl;
return 0;
}

int P = 0;
for (int i = 0; i < totalPeople; i++) {
P |= (1 << i);//把第i位设为1
}

maxCircle.clear();

bronKerbosch(0, P, 0);

sort(maxCircle.begin(), maxCircle.end(), [](int a, int b) {
return std::bitset<32>(a).count() > std::bitset<32>(b).count();
});
//存储真正独立的朋友圈
vector<int> uniCircle;
for (int Circle : maxCircle) {
bool isSubset = false;
for (int larger : uniCircle) {
if ((Circle & larger) == Circle) {
isSubset = true;
break;
}
}
if (!isSubset) {
uniCircle.push_back(Circle);
}
}
cout << uniCircle.size() << endl;
}