选OFFER，华星光电研发非电子VS方正PCB技术管培

题目1：最少纸币数量

给定一组朋友关系，统计一下该朋友关系网中的朋友圈个数。朋友圈的定义:一个朋友圈至少由3个朋友组成，且要求同一个朋友圈中的任意两个人都具有直接的朋友关系。输入描述输入一个朋友关系列表，如 Fiends =A.B],[A.C],IB,DI，其中的每一个元素 Friendsi表示 Friends[i][0)和 Friends [i][1] 是朋友关系 先输入一个数字 N 代表关系的总数，后面每条关系一行，两个成员以逗号分隔输出描述输出一个整数，表示整个关系网中朋友圈的个数补充1：Friends.length>=1，Friends.length<= 10^32：输入的总朋友个数<= 1003：输入保证 Friend[i][0]和 Friend[i][1]一定不一样，且同一关系不会反向输入，即不会同时输入[A,B] 和 [B,A]。4：不考虑子朋友圈，即当发现 [A,B,C,D]组成一个朋友圈时，[A,B,C]、[A,B,D]等子朋友圈不单独计数示例1：输入：3A,BA,CB,D输出：0示例2：输入：7A,BA,CB,CA,DD,EB,DA,E输出：3示例3：输入：6A,BA,CB,CA,DB,DD,C输出：1————————————————版权声明：本文为CSDN博主「MISAYAONE」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/misayaaaaa/article/details/155455278//bronKerbosch算法是最优解，但是对于现在的我来说好难啊！如果考试考到了还是老老实实邻接矩阵+暴力算法吧，起码简单一些的用例应该是能通过的#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;//枢顶点IDif (P != 0) {//找到P中第一个人的idfor (int i = 0; i < totalPeople; i++) {if (P & (1 << i)) {pivot = i;break;}}}//遍历P中所有不是枢轴朋友的人for (int v = 0; v < totalPeople; v++) {//检查P的第v位是否为1if (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);}}//计算新的Xint 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);// 给人分配idif (!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;}

题目1：贪吃蛇游戏模拟