1 1500ms时间能够慷慨挥霍
2 内存一般也能够挥霍，可是要记得释放用完的内存，否则可能累积到内存超限
3 BFS分层注意细节，下三角矩阵找邻接节点也要注意细节
#include#include #include using namespace std;bool* CreateMatrixGraph(const int& N){ int arraySize = N * (N + 1) / 2; bool* graph = (bool*) malloc(sizeof(bool) * arraySize); for (int i = 0; i < arraySize; i++) { graph[i] = 0; } return graph;}bool IsMatrixConnected(const int& a, const int& b, bool* graph, const int& N){ if (a == b) { return false; } if (a > b) { return (graph[a * (a + 1) / 2 + b]); } else { return (graph[b * (b + 1) / 2 + a]); }}void MatrixConnect(const int& a, const int& b, bool* graph, const int& N){ if (a >= N || b >= N) { printf("ERROR : NODE OUT OF RANGE\n"); //return; } if (IsMatrixConnected(a, b, graph, N)) { printf("ERROR : %d AND %d ALREADY CONNECTED\n", a, b); //return; } if (a == b) { printf("ERROR : THE SAME VERTICE\n"); //return; } if (a > b) { graph[a * (a + 1) / 2 + b] = 1; } else { graph[b * (b + 1) / 2 + a] = 1; }}void GetAdjoinVertice(const int& vertice, bool* graph, int* adjoinVertice, int N){ int currentIndex = 0; // 横行计算 const int VERTICALPRIMEINDEX = (vertice*vertice + vertice) / 2; for (int j = 0; j <= vertice; j++) // 共遍历了(vertice+1)个元素 { if (graph[VERTICALPRIMEINDEX + j] == 1) { adjoinVertice[currentIndex++] = j; } } // 竖向计算初始位置。该位置是横向计算的最后一个位置 const int COLUMNPRIMEINDEX = (vertice*vertice + vertice) / 2 + vertice; for (int j = 0; j < N - vertice - 1; j++) { if (graph[COLUMNPRIMEINDEX + (j+1) * (vertice+1) + (j*j + j) / 2] == 1) { adjoinVertice[currentIndex++] = vertice + j + 1; } }}int BFS(bool* graph, int vertice, bool* isVisited, int N){ // 找vertice的朋友 queue t; t.push(vertice); isVisited[vertice] = true; // 近处的朋友包含自己我也是醉的不行 int closeFriendship = 1; int lastLevelFriend = 0; int currentLevel = 0; int currentLevelFriend = 0; while (!t.empty()) { int currentVertice = t.front(); t.pop(); //printf("%d ", currentVertice); int* adjoinVertice = (int*) malloc(sizeof(int) * N); for (int i = 0; i < N; i++) { adjoinVertice[i] = -1; } GetAdjoinVertice(currentVertice, graph, adjoinVertice, N); int i = 0; // 假设上层朋友数已经为0，即当前层遍历已经结束，将当前层朋友数设为上层朋友数。然后当前层朋友数置0 if (lastLevelFriend == 0) { currentLevel++; lastLevelFriend = currentLevelFriend; currentLevelFriend = 0; } if (currentLevel > 6) { return closeFriendship; } // 遍历当前层的朋友 while (adjoinVertice[i] != -1) { if (!isVisited[adjoinVertice[i]]) { t.push(adjoinVertice[i]); isVisited[adjoinVertice[i]] = true; closeFriendship++; currentLevelFriend++; } i++; } if (lastLevelFriend > 0) { lastLevelFriend--; } free(adjoinVertice); } return closeFriendship;}int main(){ int N; int M; scanf("%d %d", &N, &M); N++; bool* graph = CreateMatrixGraph(N); for (int i = 0; i < M; i++) { int node1;s int node2; scanf("%d %d", &node1, &node2); MatrixConnect(node1, node2, graph, N); } bool* isVisited = (bool*) malloc(sizeof(bool) * N); // 输出 for (int m = 1; m <= N - 1; m++) { for (int i = 0; i < N; i++) { isVisited[i] = false; } float closeFriend = BFS(graph, m, isVisited, N); float percent = closeFriend / (N - 1) * 100; printf("%d: %.2f%%\n", m, percent); } return 0;}