题解 | #幼儿园分班#
幼儿园分班
http://www.nowcoder.com/practice/e503f18d56754ad9bcf8631adf63721d
//其实就是判断是不是二分图，直接用染色法就好了
import java.util.*;
public class Main{
static int n, m, N = 1000, M = 2 * 1000, idx;
static int[] h = new int[N], e = new int[M], ne = new int[M];
static int[] color = new int[N];
static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt(); m = in.nextInt();
Arrays.fill(h, -1);
for(int i = 1; i <= m; i ++) {
int a = in.nextInt(), b = in.nextInt();
add(a, b); add(b, a);
}
boolean flag = dfs(1, 1);
if(flag == true)
System.out.println(1);
else
System.out.println(0);
}
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, -c))
return false;
}else if(color[j] == c)
return false;
}
return true;
}
}
查看21道真题和解析
