ProblemSet of Graph Algorithms

二分图算法

import java.util.Scanner;
 
public class Main
{
    public static int n_vertex;
    public static int n_edges;
    public static int[][] adjMatrix;
    public static int[] color;
     
    public static boolean dfs(int v,int c)
    {
        color[v]=c;
        for(int i=1;i<=n_vertex;i++)
        {
            if(adjMatrix[v][i]==1)
            {
                if(color[i]==c)
                    return false;
                if(color[i]==0 && !dfs(i,-c))
                    return false;
            }
        }
        return true;
    }
     
     
    public static String solve()
    {
        for(int i=1;i<=n_vertex;i++)
        {
            if(color[i]==0)
            {
                if(!dfs(i,1))
                {
                    return "No";
                }
            }
        }
        return "Yes";
    }
     
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        n_vertex=in.nextInt();
        n_edges=in.nextInt();
        color=new int[n_vertex+1];
        adjMatrix=new int[n_vertex+1][n_vertex+1];
        for(int i=0;i<n_edges;i++)
        {
            int start=in.nextInt();
            int end=in.nextInt();
            adjMatrix[start][end]=1;
            adjMatrix[end][start]=1;
        }
        System.out.println(solve());
    }
}