Timus #1080 Mapping color (简易图论 DFS BFS)

Map Coloring
Time limit: 1.0 second
Memory limit: 64 MB
We consider a geographical map with N countries numbered from 1 to N (0 < N < 99). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to color the map only in two colors — red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring is impossible.
Input
On the first line is written the number N. On the following N lines, the i-th line contains the countries to which the i-th country is connected. Every integer on this line is bigger than i, except the last one which is 0 and marks that no more countries are listed for country i. If a line contains 0, that means that the i-th country is not connected to any other country, which number is larger than i.
Output
The output contains exactly one line. If the coloring is possible, this line must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the color of the i-th country. 0 corresponds to red color, and one — to blue color. If a coloring is not possible, output the integer −1.
Sample

本题使用DFS或BFS可快速解答，源码如下

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class q1080 {
    public static int[][] map;
    public static int[] color;
    public static boolean flag = false;
    public static void DFS(int index,int size){
        if(flag) return;
        for(int i = 0 ;i < size;i++){
            if(map[index][i] == 1){
                if(color[i] == -1){
                    color[i] = color[index]==0?1:0;
                    DFS(i,size);
                }else if(color[i] == color[index]){
                    flag = true;
                    return;
                }
            }
        }
    }
    public static void BFS(int index,int size){
        if(flag) return;
        Queue<Integer> que = new LinkedList<>();
        que.offer(index);
        while(!que.isEmpty()){
            int cur = que.poll();
            int c = color[cur]==0?1:0;
            for(int i = 0;i < size;i++){
                if(map[cur][i] == 1){
                    if(color[i] == -1){
                        color[i] = c;
                        que.offer(i);
                    }else if(color[i] == color[cur]){
                        flag = true;
                        return;
                    }
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        map = new int[n][n];
        color = new int[n];
        for(int i = 0;i < n;i++){
            color[i]  = -1;
        }
        for(int i = 0;i<n;i++){
            while(true){
                int index = s.nextInt()-1;
                if(index == -1) break;
                map[i][index] = 1;
                map[index][i] = 1;
            }
        }
        for(int i = 0;i < n;i++){
            if(color[i]==-1){
                color[i] = 0;
                BFS(i,n);
              //DFS(i,n);
            }
        }
        if(flag){
            System.out.println(-1);
        }else{
            for(int i = 0;i<n;i++){
                System.out.print(color[i]);
            }
        }

    }
}