1 1500ms时间能够慷慨挥霍
2 内存一般也能够挥霍，可是要记得释放用完的内存，否则可能累积到内存超限
3 BFS分层注意细节，下三角矩阵找邻接节点也要注意细节
#include <iostream>
#include <malloc.h>
#include <queue>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<int> 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，即当前层遍历已经结束，将当前层朋友数设为上层朋友数。然后当前层朋友数置0if (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;sint 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;
}