Найдите два набора вершин с минимальной разностью графа, если он двудольный - PullRequest
Новая
       30

Найдите два набора вершин с минимальной разностью графа, если он двудольный

0 голосов
/ 27 марта 2019

Учитывая график учеников и их отношения друг с другом, мне нужно разделить их на две группы, чтобы в одной группе не было друзей, а разница между группами была минимизирована.

Введите

  1. Первая строка:
    • Количество студентов N и количество отношений M
  2. Следующие М строк
    • дружба между двумя учениками

выход

-группа (1 или 2) каждого учащегося

Например. Входные данные: 

6 4
1 2
1 3
4 6
4 5

Выход: 

122211

Если решения нет, выведите -1

Ограничения

  • В наших тестах мы имеем 2 ≤ N ≤ 1000 и 1 ≤ M ≤ 100000

  • В 30% тестовых случаев N ≤ 16

  • В других 20% тестовых случаев число возможных способов группирования студентов меньше или равно 10000.

Я пробовал базовую BFS, проходя через каждого студента и назначая им разные группы в зависимости от их уровня на графике, но я не уверен, как получить минимальную разницу. 

import java.util.*;

class Bipartite {

    private static int V = 6;

    // This function returns true if graph
    // G[V][V] is Bipartite, else false
    private static boolean isBipartiteUtil(int[][] G, int src,
                                           int[] colorArr) {
        colorArr[src] = 1;

        // Create a queue (FIFO) of vertex numbers and
        // enqueue source vertex for BFS traversal
        LinkedList<Integer> q = new LinkedList<>();
        q.add(src);

        // Run while there are vertices in queue
        // (Similar to BFS)
        while (!q.isEmpty()) {
            // Dequeue a vertex from queue
            int u = q.poll();

            // Return false if there is a self-loop
            if (G[u][u] == 1)
                return false;

            // Find all non-colored adjacent vertices
            for (int v = 0; v < V; ++v) {
                // An edge from u to v exists and
                // destination v is not colored
                if (G[u][v] == 1 && colorArr[v] == -1) {
                    // Assign alternate color to this
                    // adjacent v of u
                    colorArr[v] = 1 - colorArr[u];
                    q.push(v);
                }

                // An edge from u to v exists and
                // destination v is colored with same
                // color as u
                else if (G[u][v] == 1 && colorArr[v] ==
                        colorArr[u])
                    return false;
            }
        }

        // If we reach here, then all adjacent vertices
        // can be colored with alternate color
        return true;
    }

    // Returns true if G[][] is Bipartite, else false
    private static String isBipartite(int[][] G) {
        // Create a color array to store colors assigned
        // to all veritces. Vertex/ number is used as
        // index in this array. The value '-1' of
        // colorArr[i] is used to indicate that no color
        // is assigned to vertex 'i'. The value 1 is used
        // to indicate first color is assigned and value
        // 0 indicates second color is assigned.
        int[] colorArr = new int[V];
        for (int i = 0; i < V; ++i)
            colorArr[i] = -1;

        // This code is to handle disconnected graoh
        for (int i = 0; i < V; i++)
            if (colorArr[i] == -1)
                if (!isBipartiteUtil(G, i, colorArr))
                    return "-1";
        String line = "";
        for (int i = 0; i < V; i++) {
            line = line + (colorArr[i] + 1);
        }

        return line;
    }

    /* Driver program to test above function */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[][] G = {{0, 1, 1, 0, 0, 0},
                {1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 1},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0, 0}};

        System.out.println(isBipartite(G));
    }
}

Я все еще получаю результат, но это не минимальная разница. Для приведенного выше примера я бы получил 

122122 //Difference of 2

в отличие от 

122211 //Difference of 0
...