Solving Graph Problems (Part 1) - Basic

Solving graph problems for newbies was never been easy. In this series of blog, I am going to delineate solutions of graph problems precisely taken from several online judges which will help newbies to solve graph problem from easy to hard categories. Although It's good to have a theoritical background before solving graph problems like - strongly connected graph, sparse graph, densed graph, I guess these anyone could learn these stuffs by solving problems too. Anyway here I am going to code in Java and C++.

Graph Representations:

Proper graph representations are essential to solve graph problems. There are 2 types of graph representations:

1. Adjacency Matrix: In adjacency matrix there is a 2D array with dimension NxN where N is the number of nodes/vertices in the graph. If A is the adjacency matrix then each element of the array with index A[i][j] indicates existance of edge between i and j. For unweighted graph this value could be only 0 and 1. For weighted graph this could be weight of the edge between i and j. Note that in this representation, you need the 2D array always doesn't matter how many edges exist in graph. If number of edges is few but number of nodes are high (a.k.a. sparse graph) then most of the element of the array will be empty. So this representation is inefficient and requires much space in many cases and should be avoided. Example:

2. Adjacency List: Adjacency list is a list of edges maintained per node/vertice. For each vertice i there is a linked list and each element of the linked list contains another vertice number j. So edge exists from i to all elements of linked list. For unweighted graph, each node of linked list contains only vertice number. For weighted graph each node of linked list contains both vertice number and weight of the edge. Example:

Solving 1st graph problem (Bipartite Check):

Problem Source: UVA Online Judge - 10004

Brief Analysis: Given a graph with adjacency list representation this problem asked to check is the graph Bipartite or not.

Java Code:

public class Main {

    static int NODE, EDGE;
    static List<Integer>[] G;
    static int color[];

    static boolean isBipartite(int u, int c) {
        color[u] = c;
        c = (c == 1 ? 2 : 1);

        boolean ret = true;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u].get(i);
            if (color[v] == 0) ret = isBipartite(v, c);
            else if (color[v] == color[u]) return false;
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner scanner = inputFromSystem();

        while (scanner.hasNextInt()) {
            NODE = scanner.nextInt();
            if (NODE == 0) break;

            EDGE = scanner.nextInt();

            G = new ArrayList[NODE];
            for (int i = 0; i < NODE; i++) G[i] = new ArrayList<>();
            color = new int[NODE];

            for (int i = 0; i < EDGE; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                G[u].add(v);
                G[v].add(u);
            }

            System.out.printf("%s\n", isBipartite(0, 1) ? "BICOLORABLE." : "NOT BICOLORABLE.");
        }
    }

    static Scanner inputFromFile() {
        Scanner scanner = null;
        try {
            scanner = new Scanner(new FileInputStream("input.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return scanner;
    }

    static Scanner inputFromSystem() {
        return new Scanner(System.in);
    }
}
Solving 2nd graph problem (Flood-Fill):

Problem Source: UVA Online Judge - 10336

Brief Analysis: Straight-forward flood-fill problem. Need to count similar types of connected components and print them descending order.

Java Code:

public class Main {

    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;

    static final int dx[] = {-1,  0, 1, 0};
    static final int dy[] = { 0, -1, 0, 1};

    static int H, W;
    static char grid[][];
    static char color[][];
    static Lang langs[];

    static void DFS() {
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++) {
                if (color[i][j] == WHITE) {
                    char ch = grid[i][j];
                    floodFill(i, j, ch);
                    langs[ch - 'a'].name = ch;
                    langs[ch - 'a'].count++;
                }
        }
    }

    static int floodFill(int x, int y, char ch) {
        int ret = 1;
        color[x][y] = GRAY;

        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue;

            if (grid[nx][ny] == ch && color[nx][ny] == WHITE) ret += floodFill(nx, ny, ch);
        }

        return ret;
    }

    static class Lang {
        char name;
        int count;
    }

    public static void main(String[] args) {
        Scanner scanner = inputFromSystem();

        int TC, tc;

        TC = scanner.nextInt();

        for (tc = 1; tc <= TC; tc++) {
            H = scanner.nextInt();
            W = scanner.nextInt();

            grid = new char[H][W];
            color = new char[H][W];
            langs = new Lang[26];
            for (int i = 0; i < langs.length; i++) langs[i] = new Lang();

            for (int i = 0; i < H; i++) {
                String line = scanner.next();
                for (int j = 0; j < W; j++) {
                    grid[i][j] = line.charAt(j);
                }
            }

            DFS();
            Arrays.sort(langs, (Lang o1, Lang o2) -> {
                if (o1.count == o2.count) return o1.name - o2.name;
                return o2.count - o1.count;
            });

            System.out.println("World #" + tc);
            for (int i = 0; i < 26; i++) {
                if (langs[i].count == 0) break;
                System.out.printf("%c: %d\n", langs[i].name, langs[i].count);
            }
        }
    }

    static Scanner inputFromFile() {
        Scanner scanner = null;
        try {
            scanner = new Scanner(new FileInputStream("input.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return scanner;
    }

    static Scanner inputFromSystem() {
        return new Scanner(System.in);
    }
}

Few others flood-fill problems:

  1. UVA Online Judge - 469
  2. UVA Online Judge - 1110
  3. UVA Online Judge - 11518
  4. UVA Online Judge - 11561
  5. UVA Online Judge - 10707
Blog Comments powered by Disqus.

Next Post Previous Post