Graph Coloring Count Problem

Problem Statement

Given an undirected graph, color each vertex such that no two adjacent vertices share the same color. Calculate the total number of valid coloring schemes using a specified number of colors.

Input Format

1. First line: Two positive integers n and m (0 < n, m < 100), representing the number of vertices and edges of the graph.
2. Second line: A positive integer k, the count of available colors (colors are labeled with positive integers starting from 1).
3. Next m lines: Each line contains two integers x and y, indicating an undirected edge between vertex x and vertex y (vertices are numbered starting from 1).

Output Format

Output the total number of valid coloring schemes for the given graph and color count.

Problem Analysis

1. Validity Check: For the current vertex, verify if selecting a given color would create a conflict with any already-colored adjacent vertices.
2. DFS Traversal: Process vertices sequentially from 1 to n. For each vertex, iterate through all available colors, validate the color, assign it to the vertex, then recursively process the next vertex. After returning from the recursive call, backtrack by unassigning the color from the current vertex. Each time all vertices are successfully colored, increment the total valid scheme count.

#include <iostream>
using namespace std;

const int MAX_SIZE = 110;
bool adj_matrix[MAX_SIZE][MAX_SIZE] = {false};
int vertex_colors[MAX_SIZE] = {0};
int total_vertices, total_edges, color_count, total_schemes = 0;

bool is_color_valid(int current_node, int chosen_color) {
    for (int i = 1; i <= total_vertices; ++i) {
        if (adj_matrix[current_node][i] && vertex_colors[i] == chosen_color) {
            return false;
        }
    }
    return true;
}

void dfs_color(int current_node) {
    if (current_node > total_vertices) {
        total_schemes++;
        return;
    }
    for (int c = 1; c <= color_count; ++c) {
        if (is_color_valid(current_node, c)) {
            vertex_colors[current_node] = c;
            dfs_color(current_node + 1);
            vertex_colors[current_node] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> total_vertices >> total_edges;
    cin >> color_count;
    
    int u, v;
    for (int i = 0; i < total_edges; ++i) {
        cin >> u >> v;
        adj_matrix[u][v] = adj_matrix[v][u] = true;
    }
    
    dfs_color(1);
    cout << total_schemes << '\n';
    return 0;
}

Minimal Exam Hall Allocation Problem

Problem Statement

There are n students attending an exam. No two students who know each other can be assigned to the same exam hall. Calculate the minimum number of exam halls required to comply with this rule.

Input Format

1. First line: Integer n, the total number of students.
2. Second line: Integer m, the number of mutual acquaintance pairs.
3. Next m lines: Each line contains two integers a and b, indicating that student a and student b know each other.

Output Format

Output the minimum number of exam halls needed to seat all students without violating the acquaintance rule.

Problem Analysis

1. State Tracking: Use a depth-first search to track the current student being assigned and the number of exam halls already opened.
2. Pruning Optimization: If the current number of halls used exceeds the best solution found so far, terminate the current search branch early to avoid unnecessary computations.
3. Assignment Logic: For each current student, first check all existing halls: if the student has no acquaintances in a hall, assign them to that hall and proceed to the next student, then backtrack by removing the student from the hall. If no existing hall is suitable, open a new hall for the student, proceed, then backtrack. When all students are assigned, update the best solution if the current hall count is lower than the previously recorded minimum.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_SIZE = 110;
bool acquaintance[MAX_SIZE][MAX_SIZE] = {false};
int total_students, min_halls = MAX_SIZE;
vector<int> exam_rooms[MAX_SIZE];

void dfs_assign(int current_student, int current_room_count) {
    if (current_room_count >= min_halls) {
        return;
    }
    if (current_student > total_students) {
        min_halls = current_room_count;
        return;
    }
    // Try placing current student in existing rooms
    for (int r = 1; r <= current_room_count; ++r) {
        bool can_place = true;
        for (int peer : exam_rooms[r]) {
            if (acquaintance[current_student][peer]) {
                can_place = false;
                break;
            }
        }
        if (can_place) {
            exam_rooms[r].push_back(current_student);
            dfs_assign(current_student + 1, current_room_count);
            exam_rooms[r].pop_back();
        }
    }
    // Open new room for current student
    exam_rooms[current_room_count + 1].push_back(current_student);
    dfs_assign(current_student + 1, current_room_count + 1);
    exam_rooms[current_room_count + 1].pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> total_students >> total_edges;
    int a, b;
    for (int i = 0; i < total_edges; ++i) {
        cin >> a >> b;
        acquaintance[a][b] = acquaintance[b][a] = true;
    }
    
    dfs_assign(1, 0);
    cout << min_halls << '\n';
    return 0;
}