-
奇数环:由奇数条边形成的一个环
-
二分图:当且仅当图中不含有奇数环,两个集合内部的内部没有边
算法1
使用bfs
- 约定染的颜色有1颜色和2颜色
时间复杂度 $O(m + n)$
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int n;
static int m;
static int N = 100010;
static int M = 200010;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static int[] color = new int[N];//共1和2两种不同的颜色
static boolean[] st = new boolean[N];
public static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static boolean bfs()
{
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 1;i <= n;i++)
{
//若该点为未色
if(color[i] == 0)
{
color[i] = 1;
queue.add(i);
while(!queue.isEmpty())
{
int t = queue.poll();
for(int j = h[t] ;j != -1;j = ne[j])
{
int k = e[j];
if(color[k] == 0)
{
color[k] = 3 - color[t];
queue.add(k);
}
else if(color[k] == color[t]) return false;
}
}
}
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
add(a,b);
add(b,a);
}
if(bfs()) System.out.println("Yes");
else System.out.println("No");
}
}
算法2
使用dfs(注意:在这里使用java会直接爆栈hh)
- dfs(u,c)表示把u号点染色成c颜色,并且判断从u号点开始染其他相连的点是否染成功
时间复杂度 $O(m + n)$
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int n;
static int m;
static int N = 100010;
static int M = 200010;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static int[] color = new int[N];//共1和2两种不同的颜色
static boolean[] st = new boolean[N];
public static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
//dfs(u,c)表示把u号点染色成c颜色,并且判断从u号点开始染其他相连的点是否成功
public static boolean dfs(int u,int c)
{
color[u] = c;
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(color[j] == 0)
{
if(!dfs(j,3 - c)) return false;
}
else if(color[j] == c) return false;//颜色重复
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
add(a,b);
add(b,a);
}
boolean flag = true;//标记是否染色成功
for(int i = 1;i <= n;i++)
{
//若未染色
if(color[i] == 0)
{
if(!dfs(i,1))
{
flag = false;
break;
}
}
}
if(flag) System.out.println("Yes");
else System.out.println("No");
}
}
为什么这李ne【】和e【】要创建2倍于N的空间
无向图,每条边要存两遍
https://blog.csdn.net/WJPnb1/article/details/126332263?spm=1001.2014.3001.5501 第一次写csdn博客,写了这个找二分图最大匹配的,大家可以来看看,有问题交流交流
呆呆,我爱你!
巨巨 ,假设图中有边自环, 1–1 1–4 4–2 2–3 是二分图嘛?
肯定不是塞,看看它的定义:将所有点分成两个集合,使得所有边只出现在集合之间,就是二分图。边只能出现在集合之间,不能出现在集合之内,或者你用刚刚写的染色法判断下,输出为NO就不是二分图~
java的同学还是需要照顾的哇
呆呆yyds
你这个dfs也可以过呀
Java确实存在暴栈问题。现在在评测时将Java的默认栈空间提升到了16MB,已经不存在暴栈的问题了。这份是AC代码,可以参考一下:AcWing 860. 染色法判定二分图。
y总原话
orz
tql