题解 | #图的闭包#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int id, degree;
    Node(int i = 0, int d = 0) : id(i), degree(d) {}
    bool operator<(const Node& other) const {
        return degree > other.degree;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    // 初始化邻接矩阵和节点数组
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
    vector<Node> nodes(n + 1);
    for(int i = 1; i <= n; i++) {
        nodes[i].id = i;
    }
    
    // 读入边并更新度数
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u][v] = graph[v][u] = 1;
        nodes[u].degree++;
        nodes[v].degree++;
    }
    
    int ans = 0;
    // 需要两次遍历
    for(int k = 0; k < 2; k++) {
        for(int i = 1; i <= n; i++) {
            sort(nodes.begin() + i, nodes.end());
            for(int j = i + 1; j <= n; j++) {
                auto& u = nodes[i];
                auto& v = nodes[j];
                if(u.degree + v.degree >= n && !graph[u.id][v.id]) {
                    graph[u.id][v.id] = graph[v.id][u.id] = 1;
                    u.degree++;
                    v.degree++;
                    ans++;
                }
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while ((str = br.readLine()) != null) {
            if (str.equals("")) continue;
            String[] params = str.split(" ");
            int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
            int[][] A = new int[n+1][n+1];
            int[] degree = new int[n+1];
            for (int i = 0; i < m; i++) {
                params = br.readLine().split(" ");
                int u = Integer.parseInt(params[0]), v = Integer.parseInt(params[1]);
                A[u][v] = A[v][u] = 1;
                degree[u]++;
                degree[v]++;
            }
             
            int ans = 0;
            boolean[] seen = new boolean[n+1];
            for (int i = 0; i < n; i++) {
                int index = 0, max = 0;
                // 先找出未被遍历过的节点中度最大的
                for (int j = 1; j <= n; j++) {
                    if (seen[j] || degree[j] <= max) continue;
                    max = degree[j];
                    index = j;
                }
                 
                if (index == 0) break;
                seen[index] = true;
                // 找到与index不相连的，若二者的度之和大于等于n，则进行连线
                for (int j = 1; j <= n; j++) {
                    if (A[index][j] == 1 || index == j || degree[index] + degree[j] < n) continue;
                    A[index][j] = A[j][index] = 1;
                    degree[index]++;
                    degree[j]++;
                    ans++;
                }
            }
            System.out.println(ans);
        }
        br.close();
    }
}

class Node:
    def __init__(self, id=0, degree=0):
        self.id = id
        self.degree = degree
    
    def __lt__(self, other):
        return self.degree > other.degree

n, m = map(int, input().split())

# 初始化邻接矩阵和节点数组
graph = [[0] * (n + 1) for _ in range(n + 1)]
nodes = [Node(i) for i in range(n + 1)]

# 读入边并更新度数
for _ in range(m):
    u, v = map(int, input().split())
    graph[u][v] = graph[v][u] = 1
    nodes[u].degree += 1
    nodes[v].degree += 1

ans = 0
# 需要两次遍历
for _ in range(2):
    for i in range(1, n + 1):
        nodes[i:] = sorted(nodes[i:])
        for j in range(i + 1, n + 1):
            u, v = nodes[i], nodes[j]
            if u.degree + v.degree >= n and not graph[u.id][v.id]:
                graph[u.id][v.id] = graph[v.id][u.id] = 1
                u.degree += 1
                v.degree += 1
                ans += 1

print(ans)