二分图（染色法）

QingYi.

[Java] 纯文本查看 复制代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int n , m ,idx;
    static int N = 2000010;
    static int [] e = new int[N];
    static int [] ne = new int[N];
    static int [] h = new int[N];
    //当前的颜色 0 1 2
    static int [] color = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bf.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        Arrays.fill(h,-1);
        while (m-- > 0){
            String[] res = bf.readLine().split(" ");
            int a = Integer.parseInt(res[0]);
            int b = Integer.parseInt(res[1]);
            //无向图，两条边
            add(a,b);
            add(b,a);
        }
        boolean flag = true;
        for(int i = 1;i<=n;i++){
            //如果当前的color没被用过，进入dfs
            if (color[i]==0){
                //从当前的点去染1
                boolean rs = dfs(i,1);
                //如果返回的是false 直接输出false了
                if (!rs){
                    flag = false;
                    break;
                }
            }
        }
       if (flag){
           System.out.println("Yes");
       }else {
           System.out.println("No");
        }
    }

    private static boolean dfs(int curNode, int c) {
        //首先设置好当前的颜色
        color[curNode] = c;
        //开始循环遍历
        for(int i = h[curNode];i!=-1;i = ne[i]){
            int next = e[i];
            //如果当前的color是0 表示没有访问过
            if (color[next]==0){
                //如果是1 下次进入dfs的是2； 反之亦然，确实很巧妙
                if (!dfs(next,3-c)){
                    return false;
                }
                //如果当前颜色和传进来的颜色相同的话，也是false
            }else  if (color[next]==c){
                return false;
            }
        }
        return true;
    }

    private static void add(int a, int b) {
        e[idx]  = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

列明

這java看起來就好像是加了花括號的python。
我有一個想法：
以後是不是可以一鍵將Java轉成python，
或者是一鍵將python轉成Java。

马云爱逛京东

列明 发表于 2021-1-8 22:27
這java看起來就好像是加了花括號的python。
我有一個想法：
以後是不是可以一鍵將Java轉成python，

我记得有一个python的库，可以直接在Python里面使用Java代码

huamu

mark,研究研究

QingYi.

列明 发表于 2021-1-8 22:27
這java看起來就好像是加了花括號的python。
我有一個想法：
以後是不是可以一鍵將Java轉成python，

哈哈，我还没有看见有这种软件