首页 > 图论 > 二分图 > 二分图判断-Problem A.Bad Horse(codejam)
2014
08-20

二分图判断-Problem A.Bad Horse(codejam)

题目

链接:http://gcj-prod.appspot.com/codejam/contest/2933486/dashboard

题目来自 Google codejam :Practice Round China New Grad Test 2014 Problem A. Bad Horse

此题其实就是一个判断一个图是否是二分图。

二分图的定义  

设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。也就是说在二分图中,顶点可以分为两个集合X和Y,每一条边的两个顶点都分别位于X和Y集合中。如下图所示:

Bipartite1

无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。可以将U 和 V当做 着色图U中所有节点为蓝色,V中所有节点着绿色,每条边的两个端点的颜色不同,符合图着色问题的要求。相反,用这样的着色方式对非二分图是行不通的,根据triangle:其中一个顶点着蓝色并且另一个着绿色后,三角形的第三个顶点与上述具有两个颜色的顶点相连,无法再对其着蓝色或绿色。

例如对于下面的图,可以用两种颜色进行着色。

 

Bipartite2

下面的图则不可以:

Bipartite3

可以使用回溯法解决图的M着色问题,但是对个这个特殊的问题,可以使用 BFS解决。算法过程为:借助队列,进行宽度优先遍历,先对一个起点着色RED,然后将其所有相邻的节点着色为BLUE,并加入队列。只要能保证相邻的节点是不同的颜色即可。

下面的Java代码是针对 Bad Horse 的题解,大家可以只关注isBipartite函数

public class BasHorse {
	static int n;
	static int T, index, cnt;
	static int map[][];

	public static void main(String[] args) {
		try {
			String path = "D:\\CPP\\code-jam\\A-small-practice-2.in";
			Scanner scan = new Scanner(new File(path));
			String outputPath = path.replace(".in", "out.txt");
			File file = new File(outputPath);
			FileOutputStream fos = new FileOutputStream(file);
			T = scan.nextInt();
			Map<String,Integer> mapSet = new HashMap<String,Integer>();
			for(int i=0; i<T; i++){
				mapSet.clear();
				n = scan.nextInt();
				index = 0;
				map = new int[n*2][n*2];//最多会有2n个
				for(int j =0; j<n; j++){
					String str1 = scan.next();
					Integer a ;
					if( (a = mapSet.get(str1)) == null){
						a = index;
						mapSet.put(str1, index);
						index++;
					}
					String str2 = scan.next();
					Integer b ;
					if( (b = mapSet.get(str2)) == null){
						b = index;
						mapSet.put(str2, index);
						index++;
					}
					map[a][b] = 1;
					map[b][a] = 1;

				}
				boolean isbit = isBipartite(map,index);
				String output = "Case #" + (i+1) + ": ";
				if(isbit) output += "Yes\r\n";
				else output += "No\r\n";
				try {
					fos.write(output.getBytes());
				} catch (IOException e) {
					e.printStackTrace();
				}
				System.out.println(isbit);
			}

		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	private static boolean isBipartite(int[][] map,int n) {
		//colorArr[i] 代表第i个结点的颜色
		int colorArr[] = new int[n];
		colorArr[0] = 1;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(0);
		while(!queue.isEmpty()){
			int top = queue.poll();
			for(int i=0; i<n; i++){
				if(map[top][i] == 1 && colorArr[i] == 0){
					colorArr[i] = 3 - colorArr[top];//两种颜色 1和2 交替着色
					queue.add(i);
				}else if(map[top][i] == 1 &&  colorArr[i] == colorArr[top] ){
					return false;
				}
			}
		}
		return true;
	}
}

上面代码的复杂度为 O(V^2), V是图的顶点的个数。代码可以优化为使用邻接表存储图。


  1. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了