#define MAX_SIZE 1000
int VERTEX_COUNT = 0;
bool **adjacencyMatrix(){
bool **Matrix = (bool **)malloc(sizeof(bool *) * MAX_SIZE);
for(int i = 0; i <>
Matrix[i] = (bool *)malloc(sizeof(bool) * MAX_SIZE);
}
for (int i = 0; i <>
for (int j = 0; j <>
Matrix[i][j] = 0;
}
}
return Matrix;
}
void freeMatrix(bool **Matrix){
for(int i = 0; i <>
free(Matrix[i]);
}
free(Matrix);
}
void readInput(bool **Matrix){
int a, b;
printf("get ready");
while(scanf("%d %d",&a, &b)){
VERTEX_COUNT = VERTEX_COUNT > b ? VERTEX_COUNT : b;
Matrix[a][b] = 1;
Matrix[b][a] = 1;
}
VERTEX_COUNT ++;
}
int *getDegree(bool **Matrix){
int *degree = malloc(sizeof(int) *VERTEX_COUNT);
for (int i = 0; i <>
degree[i] = 0;
}
for (int i = 0; i < vertex_count;="">
for (int j = 0; j < vertex_count;="">
if (Matrix[i][j] == 1){
degree[i]++;
}
}
}
return degree;
}
bool **deleteVertex(bool **Matrix, int vertextodelete){
for (int i = 0; i <>
Matrix[i][vertextodelete] = 0;
}
for (int j = 0; j <>
Matrix[vertextodelete][j] = 0;
}
return Matrix;
}
bool **k_core_degeneracy(int k, bool **Matrix){
bool **resultMatrix = malloc(sizeof(bool *) * VERTEX_COUNT);
for (int i = 0; i <>
resultMatrix[i] = malloc(sizeof(bool) * VERTEX_COUNT);
}
for (int i = 0; i <>
for (int j = 0; j <>
resultMatrix[i][j] = Matrix[i][j];
}
}
while(1){
int *degree = getDegree(resultMatrix);
int count = 0;
for (int i = 0; i <>
if(degree[i]
count++;
}
}
if(count==0){
free(degree);
break;
}
for (int i = 0; i
if (degree[i] <>
resultMatrix = deleteVertex(resultMatrix, i);
}
}
free(degree);
}
return resultMatrix;
}
bool allzero(bool **matrix){
for (int i = 0; i <>
for (int j = 0; j <>
if(matrix[i][j]!=0){
return false;
}
}
}
return true;
}
void outputformat(bool **matrix){
for (int i = 0; i <>
for (int j = 0; j < vertex_count;="">
if(matrix[i][j]!=0 && j>i){
printf("%d %d\n", i, j);
}
}
}
}
void freeResultMatrix(bool **Matrix){
for (int i = 0; i <>
free(Matrix[i]);
}
free(Matrix);
}
int main(){
bool **Matrix = adjacencyMatrix();
printf("get ready 1");
readInput(Matrix);
bool **resultMatrix;
for (int i = 1;;i++){
resultMatrix = k_core_degeneracy(i, Matrix);
if(allzero(resultMatrix)){
freeResultMatrix(resultMatrix);
resultMatrix = k_core_degeneracy(i-1, Matrix);
printf("%d-core\n", i - 1);
break;
}
else{
freeResultMatrix(resultMatrix);
}
}
outputformat(resultMatrix);
freeMatrix(Matrix);
freeResultMatrix(resultMatrix);
return 0;
}
input is:
0 1
0 2
1 2
1 5
2 3
2 4
2 5
2 6
3 4
3 6
3 7
4 6
4 7
5 6
5 8
6 7
6 8
output is:
3-core 2 3 2 4 2 6 3 4 3 6 3 7 4 6 4 7 6 7