二分图判定

关于2019的校招题，我从头刷到这儿，碰到的第一个关于图的题。总结了一下图的写法，关于图的存储常用两种：邻接矩阵和邻接表；图的遍历有三种：BFS，DFS递归，DFS非递归。所以图的存储和图的遍历共有6种组合。从而我写了6种方法，经测试已全部AC，下面提供的6种AC代码可以交叉对比 从而对图的存储和图的遍历有个更清晰的认识

import java.util.*;
import static java.lang.System.in;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] edge = new int[m][2];
        for (int i = 0; i < m; i++) {
            edge[i][0] = sc.nextInt();
            edge[i][1] = sc.nextInt();
        }
        //arrStoreWay(edge, n);
        adjStoreWay(edge,n);
    }

    public static void arrStoreWay(int[][] data, int n) {
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 0; i < data.length; i++) {
            graph[data[i][0]][data[i][1]] = 1;
            graph[data[i][1]][data[i][0]] = 1;
        }
        //arrBFS(graph,n);
        //arrDFSRecursion(graph,n);
        arrDFSStack(graph, n);
    }

    public static void adjStoreWay(int[][] data, int n) {
        HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
        for (int i = 0; i < data.length; i++) {
            if (!graph.containsKey(data[i][0])) {
                graph.put(data[i][0], new LinkedList<>());
            }
            if (!graph.containsKey(data[i][1])) {
                graph.put(data[i][1], new LinkedList<>());
            }
            graph.get(data[i][0]).add(data[i][1]);
            graph.get(data[i][1]).add(data[i][0]);
        }
        adjBFS(graph,n);
        //adjDFSRecursion(graph,n);
        //adjDFSStack(graph,n);
    }

    public static void arrBFS(int[][] graph, int n) {
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        int[] marks = new int[n + 1];
        for (int i = 1; i < graph.length; i++) {
            //防止出现多个连通分量
            if (set.contains(i)) {
                continue;
            }
            queue.offer(i);
            marks[i] = 1;
            set.add(i);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int j = 1; j < graph[cur].length; j++) {
                    if (graph[cur][j] == 1 && marks[cur] == marks[j]) {
                        System.out.println("No");
                        return;
                    }
                    if (graph[cur][j] == 1 && !set.contains(i)) {
                        marks[j] = -marks[cur];
                        queue.offer(j);
                        set.add(j);
                    }
                }
            }
        }
        System.out.println("Yes");
    }

    public static String res = "Yes";
    public static void arrDFSRecursion(int[][] graph, int n) {
        HashSet<Integer> set = new HashSet<>();
        int[] marks = new int[n + 1];
        for (int i = 1; i < graph.length; i++) {
            if (set.contains(i)) {
                continue;
            }
            marks[i] = 1;
            set.add(i);
            arrDFSRecursionProcess(i, graph, marks, set);
        }
        System.out.println(res);
    }

    public static void arrDFSRecursionProcess(int node, int[][] graph, int[] marks, HashSet<Integer> set) {
        for (int j = 1; j < graph[node].length; j++) {
            if (graph[node][j] == 1 && marks[node] == marks[j]) {
                res = "No";
                return;
            }
            if (graph[node][j] == 1 && !set.contains(j)) {
                marks[j] = -marks[node];
                set.add(j);
                arrDFSRecursionProcess(j, graph, marks, set);
            }
        }
    }

    public static void arrDFSStack(int[][] graph, int n) {
        HashSet<Integer> set = new HashSet<>();
        int[] marks = new int[n + 1];
        Stack<Integer> stack = new Stack<>();
        for (int i = 1; i < graph.length; i++) {
            if (set.contains(i)) {
                continue;
            }
            set.add(i);
            marks[i] = 1;
            stack.push(i);
            while (!stack.isEmpty()) {
                int cur = stack.pop();
                for (int j = 1; j < graph[cur].length; j++) {
                    if (graph[cur][j] == 1 && marks[cur] == marks[j]) {
                        System.out.println("No");
                        return;
                    }
                    if (graph[cur][j] == 1 && !set.contains(j)) {
                        stack.push(cur);
                        marks[j] = -marks[cur];
                        set.add(j);
                        stack.push(j);
                        break;
                    }
                }
            }
        }
        System.out.println("Yes");
    }

    public static void adjBFS(HashMap<Integer, LinkedList<Integer>> graph,int n) {
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        int[] marks = new int[n + 1];
        for (Integer item : graph.keySet()) {
            if (set.contains(item)) {
                continue;
            }
            set.add(item);
            marks[item] = 1;
            queue.offer(item);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (Integer iitem : graph.get(cur)) {
                    if (marks[iitem] == marks[cur]) {
                        System.out.println("No");
                        return;
                    }
                    if (!set.contains(iitem)) {
                        marks[iitem] = -marks[cur];
                        queue.offer(iitem);
                        set.add(iitem);
                    }
                }
            }
        }
        System.out.println("Yes");
    }

    public static String adjRes = "Yes";
    public static void adjDFSRecursion(HashMap<Integer, LinkedList<Integer>> graph, int n) {
        HashSet<Integer> set = new HashSet<>();
        int[] marks = new int[n + 1];
        for (Integer item : graph.keySet()) {
            if (set.contains(item)) {
                continue;
            }
            set.add(item);
            marks[item] = 1;
            adjDFSRecursionProcess(item,graph,marks,set);
        }
        System.out.println(adjRes);
    }

    public static void adjDFSRecursionProcess(int node, HashMap<Integer, LinkedList<Integer>> graph, int[] marks, HashSet<Integer> set) {
        for (Integer item : graph.get(node)) {
            if (marks[item] == marks[node]) {
                adjRes = "No";
                return;
            }
            if (!set.contains(item)) {
                set.add(item);
                marks[item] = -marks[node];
                adjDFSRecursionProcess(item,graph,marks,set);
            }
        }
    }

    public static void adjDFSStack(HashMap<Integer, LinkedList<Integer>> graph, int n) {
        HashSet<Integer> set = new HashSet<>();
        int[] marks = new int[n + 1];
        Stack<Integer> stack = new Stack<>();
        for (Integer item : graph.keySet()) {
            if (set.contains(item)) {
                continue;
            }
            set.add(item);
            marks[item] = 1;
            stack.push(item);
            while (!stack.isEmpty()) {
                int cur = stack.pop();
                for (Integer iitem : graph.get(cur)) {
                    if (marks[iitem] == marks[cur]) {
                        System.out.println("No");
                        return;
                    }
                    if (!set.contains(iitem)) {
                        set.add(iitem);
                        marks[iitem] = -marks[cur];
                        stack.push(cur);
                        stack.push(iitem);
                    }
                }
            }
        }
        System.out.println("Yes");
    }
}

 AC代码
#include <bits/stdc++.h>
 using namespace std;
 const int maxn=1e5+8;
 vector<int>G[maxn];
 int V;
 int color[maxn];
 bool dfs(int v,int c){
     color[v]=c;
     for(int i=0;i<G[v].size();i++){
         if(color[G[v][i]]==c)return false;
         if(color[G[v][i]]==0&&!dfs(G[v][i],-c))return false;
     }
     return true;
 }
 void solve(){
     for(int i=0;i<V;i++){
         if(color[i]==0)
         if(!dfs(i,1)){
             printf("No\n");
             return;
         }
     }
     printf("Yes\n");
 }
 int main()
 {
     int m;
     scanf("%d%d",&V,&m);
     for(int i=0;i<m;i++){
         int s,t;
         scanf("%d%d",&s,&t);
         G[s].push_back(t);
         G[t].push_back(s);
     }
     solve();
    return 0;
 }

///很简单
//定义俩个集合
///左边放一种颜色顶点
///右边放另一种颜色顶点
//当一次输入时一个集合同时出现俩个顶点就不能形成二分图
///求顶，谢谢，让大家看到

#include<iostream>
(720)#include<unordered_map>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int i=0;
    int s,t;
    unordered_map<int,int> p;
    unordered_map<int,int> q;
    while(i<m)
    {
        cin>>s>>t;
        if(((p.find(s)!=p.end())&&(p.find(t)!=p.end()))||((q.find(s)!=q.end())&&(q.find(t)!=q.end())))
        {
            cout<<"No";
            return 0;
        }
        else if(p.find(s)!=p.end())
            q.insert({t,i});
        else if(p.find(t)!=p.end())
            q.insert({s,i});
        else if(q.find(s)!=q.end())
            p.insert({t,i});
        else if(q.find(t)!=q.end())
            p.insert({s,i});
        else
        {
            p.insert({s,i});
            q.insert({t,i});
        }
        i++;
    }
    cout<<"Yes";
}

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 10;

vector<int> vec[N];
int color[N];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    memset(color, -1, sizeof(color));
    auto dfs = [&](auto &&self, int u, int c) {
        color[u] = c;
        for (int v : vec[u]){
            if(color[v] == color[u]){
                return false;
            } else if(color[v] == (c ^ 1)){
                continue;
            } else if(color[v] == -1){
                if(!self(self, v, c ^ 1)){
                    return false;
                }
            }
        }
        return true;
    };
    puts(dfs(dfs, 1, 0) ? "Yes" : "No");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100007;
int n,m;
vector<int> G[N];
int a[N];

bool DFS(int u, int c){
    a[u] = c;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(a[v]==c)
            return false;
        if(a[v]==0 && !DFS(v, -c))
            return false;
    }
    return true;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bool flag = true;
    for(int i=0;i<n;i++){
        if(a[i]==0 && !DFS(i,1)){
            flag = false;
            break;
        }
    }
    cout<<(flag?"Yes":"No")<<endl;
    return 0;
}

/*
图的m着色问题(判定或求方案)，考虑DFS
以下用非递归的方法实现dfs
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10000

bool ok(vector<int> edge[], int color[], int k)
{
    for(auto it : edge[k]) {
        if(color[k] == color[it]) return false;
    }
    return true;
}

bool dfs(vector<int> edge[], int n, int m, int color[])
{
    int k = 1;
    while(k >= 1) {
        color[k] += 1;
        while(color[k] <= m) { //搜索可用的颜色
            if(ok(edge, color, k)) break;
            else color[k] += 1;
        }

        if(color[k] > m) { //回溯
            color[k] = 0;
            k--;
        } else if(k >= n) { //求解完毕，输出解
            return true;  //判定是否有可行解
//            for(i = 1; i <= n; i++)  //输出着色方案
//                printf("%d ", color[i]);
//            printf("\n");
//            return; //return表示之求解其中一种解
        } else { //处理下一个顶点
            k++;
        }
    }
    return false;
}

int main()
{
//    freopen("input.txt", "r", stdin);
    int n, k, i, u, v;
    cin >> n >> k;
    vector<int> edge[n + 1];
    for(i = 0; i < k; i++) {
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int color[n + 1];
    memset(color, 0, sizeof(color));
    int m = 2; //可用m种颜色
    if(dfs(edge, n, m, color)) printf("Yes\n");
    else printf("No\n");
    return 0;
}

print(search())

#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int N, M, s, e;
    bool res = true;
    cin>>N>>M;
    vector<int> grap(N, -1);
    for(int i = 0; i < M; ++i){
        cin>>s>>e;
        if(grap[s] == grap[e]){
            if(grap[s] != -1){
                res = false;
            }else{
                grap[s] = 0;
                grap[e] = 1;
            }
        }else if(grap[s] == -1){
            grap[s] = 1-grap[e];
        }else{
            grap[e] = 1-grap[s];
        }
    }
    cout<<(res ? "Yes" : "No")<<endl;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum { UNKNOWN = 0, BLACK = 1, WHITE = 2 } Color;

typedef struct {
  int to;
  int next;
} Edge;

void addEdge(int* head, Edge* edges, int u, int v, int i) {
  (*(edges + i)).next = *(head + u);
  (*(edges + i)).to = v;
  *(head + u) = i;
}

void printAdjList(int* head, Edge* edges, const int n) {
  int i, u;
  for (u = 1; u <= n; ++u) {
    fprintf(stdout, "vertex %d: [ ", u);
    for (i = *(head + u); i; i = (*(edges + i)).next)
      fprintf(stdout, "%d ", (*(edges + i)).to);
    fputs("]\n", stdout);
  }
  fputc(10, stdout);
}

int dfs(int* head, Edge* edges, int curr, Color color, Color* colors) {
  *(colors + curr) = color;
  int i, nei;
  for (i = *(head + curr); i; i = (*(edges + i)).next) {
    nei = (*(edges + i)).to;
    if (*(colors + nei) == color) return 0; // 我邻居的颜色与我相同，表明存在着冲突
    if (*(colors + nei) == UNKNOWN && 
        !dfs(head, edges, nei, color == BLACK ? WHITE : BLACK, colors))
      return 0;
  }
  return 1;
}

int main(const int argc, const char* argv[]) {
  int n, m, u, v;
  fscanf(stdin, "%d %d", &n, &m);
  
  int head[n + 1]; 
  Edge edges[m << 1 | 1];
  memset(head, 0x0000, sizeof head);
  
  int i = 0;
  while (m--) {
    fscanf(stdin, "%d %d", &u, &v);
    addEdge(head, edges, u, v, ++i);
    addEdge(head, edges, v, u, ++i);
  }
  
  Color colors[n + 1];
  memset(colors, UNKNOWN, sizeof colors);
  
  // 图中可能有多个连通分量 (连通分量 == 极大的连通子图)
  for (u = 1; u <= n; ++u)
    if (*(colors + u) == UNKNOWN && !dfs(head, edges, u, BLACK, colors))
      return fputs("No", stdout), 0;
  
  return fputs("Yes", stdout), 0;
}

#include <iostream>
(720)#include <vector>
using namespace std;
bool dfs(vector<int> * graphs,int *colors,int i,int s){
    colors[i]=s;
    for (auto a:graphs[i]){
        if (s==colors[a]) return false;
        if (colors[a]==0 && !dfs(graphs,colors,a,-s)) return false;
    }
    return true;
}
bool paint(vector<int>* graphs,int * colors,int n){
    for (int i=1;i<=n;i++)
        if (colors[i]==0 && !dfs(graphs,colors,i,1))
            return false;
    return true;
}
int main(){
    int n,m;
    cin>>n>>m; 
    vector<int> graphs[n+1];
    for (int i=0;i<m;i++){
        int s,t;
        cin>>s>>t;
        graphs[s].push_back(t);
        graphs[t].push_back(s);
    }
    int *colors=new int[n+1];
    if (paint(graphs,colors,n))
        cout<<"Yes";
    else 
        cout<<"No";
    return 0;
}

import java.util.*;
import static java.lang.System.in;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        int m  = sc.nextInt();
        // 建图
        HashMap<Integer, HashSet<Integer>> graph =new HashMap<>();
        
        for(int i = 0; i<m; i++){
            int curr = sc.nextInt();
            int next = sc.nextInt();
            graph.putIfAbsent(curr,new HashSet());
            graph.get(curr).add(next);
        }
        //  是n+1,因为从0开始
        int[] colors = new int[n+1];
        // 我们染色三种情况，0是没有染色到，1是一种颜色，-1是一种颜色
        boolean ans = true;
        for(int cur= 1; cur<=n; cur++){
            //对于一个从来没染过色的点，初始都为1，然后我们开始爱的魔力找圈圈
            if(colors[cur] == 0  &&  !dfs(colors,1,graph, cur ))  ans =false;
        }
        //***改的，就是为了输出简单
        String res = "Yes";
        if(!ans)  res = "No";
        
        System.out.println(res);
    }
    private static boolean dfs(int[] colors, int color, HashMap<Integer, HashSet<Integer>> graph,int cur){
       //找到了一个环，然后看他现在要给的颜色和之前的颜色是不是一样的。这个根据题意好理解。
        if(colors[cur] != 0) return colors[cur] == color;
        colors[cur] = color;
        
        //非连通图的情况，到了尾巴，发现他是个一条边，这种情况肯定是对的
        if(!graph.containsKey(cur)) return true;
        
        for(int next:  graph.get(cur)){
            if(!dfs(colors, -color, graph, next)) return false;
        }
        
        return true;
    }
}

#include <bits/stdc++.h>
using namespace std;

/*
    广度优先，给一个顶点染1，它的邻点染-1,如果发现邻点已染色且跟自己相同，则over
*/
// N<=100000 只能用邻接表法存储

struct GraphNode{
    int id;
    int color;  // 0未染色 1红 -1黑  
    vector<int> neighbors;
    GraphNode(){}
    GraphNode(int idx):id(idx),color(0){}
    GraphNode(const GraphNode &g){
        id = g.id;
        color = g.color;
    }
};

int main(){
    int N,M;
    cin>>N>>M;
    vector<GraphNode> G(N+1);
    for(int i=1;i<=N;i++){
        G[i] = GraphNode(i);
    }
    int u,v;
    for(int i=0;i<M;i++){
        cin>>u>>v;
        G[u].neighbors.push_back(v);
        G[v].neighbors.push_back(u);
    }
    queue<int> Q;
    vector<bool> visited(N+1,false);
    bool ans = true;
    for(int i=1;i<=N;i++){
        if(ans==false) break;
        if(visited[i]) continue;
        Q.push(i);
        while(!Q.empty()){
            u = Q.front();Q.pop();
            visited[u]=true;
            if(G[u].color==0)
                G[u].color = 1;
            for(auto v:G[u].neighbors){
                if(visited[v]){
                    if(G[v].color==G[u].color) {
                        ans=false;//有问题
                        break;
                    }
                    else continue;
                }
                G[v].color = -1*G[u].color;
                Q.push(v);
            }
        }
        
    }
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    class Program
    {
       //涂色问题,相邻的边无法涂成相同颜色;
        public static void Main(string[] args)
        {
            //string line;
            //while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
            Func(Console.ReadLine());
        }
        public static void Func(string line)
        {
            var s1 = line.Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
            int n = s1[0], m = s1[1];//顶点和边数
            int[,] map = new int[n + 1, n + 1];
            int[] res = new int[n + 1];
            for (int i = 0; i < m; i++)
            {
                s1 = Console.ReadLine().Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
                map[s1[0], s1[1]] = 1;
                map[s1[1], s1[0]] = 1;
            }
            Console.WriteLine(Fill(n, 1, map, res, -1) ? "Yes" : "No");
        }

        public static bool Fill(int n, int root, int[,] map, int[] res,int color)
        {
            res[root] = -color;
            bool flag = true;
            for (int i = 1; i <= n; i++)
            {
                if (map[root, i] == 1)//如果这两结点有边
                {
                    if (res[i] == 0) //如果与他相邻结点没有被填色
                    {
                        flag = flag && Fill(n, i, map, res, -color);
                        if (!flag) return false;
                    }
                    else if (res[i] == -color)//如果相邻结点被填充非正确颜色
                    {
                        return false;
                    }
                }
            }
            return true;
        } 
    }
}

from collections import deque


n, m = list(map(int, input().split()))
graph = [[0] * n for _ in range(n)]
color = [0] * n

def bfs(node):
    color[node] = 1
    queue = deque([node])
    while queue:
        node = queue.popleft()
        for i in range(n):
            if graph[node][i] == 1:
                if color[i] == 0:
                    queue.append(i)
                    color[i] = -color[node]
                if color[i] == color[node]:
                    return False
    return True

for i in range(m):
    start, end = list(map(int, input().split()))
    graph[start - 1][end - 1] = 1

flag = False
for i in range(n):
    if color[i] == 0 and not bfs(i):
        flag = True
        break
if flag:
    print("No")
else:
    print("Yes")

n,m = map(int, input().split())
dic = {}
flag = 'Yes'
k = m-1 if n<m else m #避免第一个样例的情况
for i in range(k):
    u, v = map(int, input().split())
    if u not in dic:
        dic[u] = 'b'
        dic[v] = 'w'
    else:
        if v not in dic:
            if dic[u] == 'b':
                dic[v] = 'w'
            else:dic[v] = 'b'
        else:
            if dic[u] == dic[v]:
                flag = 'No'
print(flag)

#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1e5 + 8;
vector<int>G[maxn];
int color[maxn];
bool DFS(int v, int c) {
    color[v] = c;
    for (int i = 0; i < G[v].size(); i++) {
        if (color[G[v][i]] == c) {
            return false;
        }
        if (color[G[v][i]] == 0 && !DFS(G[v][i], -c)) {
            return false;
        }
    }
    return true;
}
int main() {
    int n, m;
    //memset(color, 0, sizeof(color));
    cin >> n >> m;
    for (int i = 0; i <= n; i++) { color[i] = 0; }
    while (m--) {
        int s, t;
        cin >> s >> t;
        //无向图
        G[s].push_back(t);
        G[t].push_back(s);
    }
    //如果是连通图，则一次dfs即可访问所有位置
    //但题目没有说明，故要依次检查各个顶点的情况
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0) {
            if (!DFS(i, 1)) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    system("pause");
    return 0;
}

java代码如下