Java题解 | 小红的二分图构造

二分图即需要将集合分为两部分，每部分的度数之和相等

因此问题转化为：在集合中找到一个子集，使得子集的度数和为全部节点度数和的一半

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int halfDegree;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int nodeNum = in.nextInt();
        int[] nodeDegree = new int[nodeNum];
        int sumDegree = 0;
        for(int i = 0;i < nodeNum;i++){
            int degree = in.nextInt();
            nodeDegree[i] = degree;
            sumDegree += degree;
        }
        halfDegree = sumDegree/2;
        // 当度数和为奇数时失败
        if(sumDegree % 2 == 1){
            System.out.print(-1);
            return;
        }
        int[] status = new int[nodeNum];
        // 寻找度数和为全体度数和一半的子集
        int[] result = find(nodeDegree,status,0,0);
        if(result[0] == -1){
            System.out.print(-1);
            return;
        }
        else System.out.println(halfDegree);
        int rightPoint = 0;
        for(int leftPoint = 0;leftPoint < nodeNum;leftPoint ++){
            if(result[leftPoint] == 0)continue;
            else{
                while(nodeDegree[leftPoint] != 0){
                    while(rightPoint != nodeNum){
                        if(nodeDegree[rightPoint] != 0 && status[rightPoint] == 0)break;
                        rightPoint++;
                    }
                    System.out.println(leftPoint < rightPoint ?(leftPoint + 1) + " " + (rightPoint + 1) : (rightPoint + 1) + " " + (leftPoint + 1));
                    nodeDegree[leftPoint] --;
                    nodeDegree[rightPoint] --;
                }
            }
        }
    }
    public static int[] find(int[] nodeDegree,int[] status,int curDegree,int curPos){
        if(curPos == nodeDegree.length){
            //如果没有可行的分配方式，标记首位为-1
            status[0] = -1;
            return status;
        }
        if(curDegree == halfDegree) return status;
        if(curDegree + nodeDegree[curPos] == halfDegree){
            status[curPos] = 1;
            return status;
        }
        if(curDegree + nodeDegree[curPos] < halfDegree){
            status[curPos] = 1;
            int[] newStatus = find(nodeDegree,status,curDegree + nodeDegree[curPos],curPos + 1);
            if(newStatus[0] != -1) return newStatus;
            status[curPos] = 0;
        }
        return find(nodeDegree,status,curDegree,curPos + 1);
    }
}