Codeforces - 330B - Road Construction

Question

题目大意

给你 n 、 m ， n 代表 n 个顶点， m 代表的是 m 条边，下面 m 行每行两个数 to 、 from ，代表不能将 to 和 from 连接起来，问你最少需要连接多少对顶点，可以使得每个顶点到图中的任意一个顶点最多只需要两步，输出最少对数，以及连接的顶点，只需要输出任意一种方案。

解析

• 首先要做到这个要求，一定需要连接 n-1 条边；
• 知道了一定是 n-1 之后，只需要找出一个没有在输入数据中出现的顶点，然后从这个和每一个顶点都连接一条边即可；

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt(), m = cin.nextInt();
        boolean[] cant = new boolean[n+1]; // 1～n
        for(int i = 0; i < m; i++){
            int to = cin.nextInt();
            int from = cin.nextInt();
            cant[to] = true;
            cant[from] = true;
        }
        int conn = 0;
        for(int i = 1; i <= n; i++){
            if(!cant[i]){
                conn = i;
                break;
            }
        }
        System.out.println(n-1); 
        for(int i = 1; i <= n; i++){
            if(conn != i)
                System.out.println(conn + " " + i);
        }
    }
}

题目链接

https://codeforces.com/problemset/problem/330/B