目录

题目

思路

Code

题目

实现一段调度模块功能，将一批资源单元划分到两个隔离资源池中;某些资源单元之间存在互斥关系，例如会竟争同一段频谱、同一类加速卡、同一条转发链路，或者在同一资源池内运行会造成调度冲突;
现在有多组资源部署任务，其中第i组任务中:
有resourceCount[i]个资源单元，资源编号从1到resourceCount[i];例如 resourceCount[i]为4时，表示有4个资源，分别为资源1.2.3,4;
conficts[i]表示第组任务的互斥资源对，不能放入同一个资源池;例如conficts[i]为[(1,2),(1,3)]时，表示资源1和资源2互斥，资源1和资源3互斥;
请你判断每一组资源部署任务是否可以被划分到两个隔离资源池中，使得每一对互斥资源都位于不同资源池。对于每一组任务:
·如果可以完成划分，返回1。
，如果无法完成划分，返回0。
最终返回一个数组，其中第i个值表示第i组任务是否可以被两个资源池完全隔离。
补充说明(约束条件)
1.1 <= resourceCount.length <= 100
2.1 <=resourceCount[i]<= 10^4
3.0 <= conflicts[i].length <=2* 10^4
4. 1 <= conflicts[i][x], conflicts[i][y] <= resourceCount[i]
5.所有resourceCount[i]之和不超过 10^5
6.所有conflicts[i].length之和不超过2*10^5

输入描述
第一行输入resourceCnt，代表每一组的资源总数,使用空格分割
接下输出resourceCnt.length行，每行给出对应互斥资源对，冲突资源使用，分割，多组资源对之间用空格分割。
输出描述
最终返回一个数组，其中第i个值表示第i组任务是否可以被两个资源池完全隔离。输出使用，分割

样例1

输入

4,3,5
1,2 1,3 2,4
1,2 2,3 1,3
1,2 3,4

输出

1,0,1
说明
第1组任务 resourcecount[0]=4，表示有1,23,4资源，conficts =[(1,2),(1,3),(2,4)],表示第1组资源1和2, 1和3, 2和4两两互斥，第1组任务可以划分,例如资源1:[1,4],资源2:[2,3]
第2组任务无法划分，因为资源1、2、3两两互斥，只用两个资源池无法完成隔离。第3组任务可以划分，例如:资源池1:[1,3,5]资源池2:[2,4]
样例2

输入

2,2,4
1,2

1,2 2,3 3,4 4,1

输出

1,1,1
说明

第1组任务没有冲突，可以划分。
第2组任务中资源1和资源2分别放入不同资源池即可。
第3组任务形成偶数环，可以被两个资源池隔离

思路

BFS 染色
----------------------------------------------------
预处理：
  - 解析每组数据，根据冲突对建立邻接表 adj。
状态定义：
  - color[u]：0 未染色，1 / -1 分别表示两种颜色。
核心逻辑：
  1. 遍历所有节点（1..n），若未染色则 BFS：
     - 初始节点染 1。
     - BFS 遍历其邻接节点：未染色则染相反色，已染色则检查是否冲突。
  2. 若无冲突 → 1（可二分），否则 → 0。
复杂度：
  - 时间 O(N + M)：每个节点和每条边遍历一次。
  - 空间 O(N + M)：邻接表。
 

Code

import java.util.*;

/**
 * 资源池隔离判断 — 二分图检测（BFS 染色）
 */
public class Main {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            String first = sc.nextLine().trim();
            if (first.isEmpty()) { System.out.println(); return; }

            String[] cntParts = first.split(",");
            int m = cntParts.length;
            int[] resourceCnt = new int[m];
            for (int i = 0; i < m; i++) {
                resourceCnt[i] = Integer.parseInt(cntParts[i]);
            }

            List<String> results = new ArrayList<>();

            for (int i = 0; i < m; i++) {
                int n = resourceCnt[i];
                String line = sc.hasNextLine() ? sc.nextLine().trim() : "";
                List<int[]> edges = parseConflicts(line);

                // 过滤无效边
                List<int[]> validEdges = new ArrayList<>();
                for (int[] e : edges) {
                    int a = e[0], b = e[1];
                    if (a >= 1 && a <= n && b >= 1 && b <= n && a != b) {
                        validEdges.add(e);
                    }
                }

                results.add(isBipartite(n, validEdges) ? "1" : "0");
            }

            System.out.println(String.join(",", results));
        } catch (Exception e) {
            System.out.println();
        }
    }

    static List<int[]> parseConflicts(String line) {
        List<int[]> edges = new ArrayList<>();
        if (line.isEmpty()) return edges;
        String[] parts = line.split("\\s+");
        for (String part : parts) {
            String[] nums = part.split(",");
            int a = Integer.parseInt(nums[0]);
            int b = Integer.parseInt(nums[1]);
            edges.add(new int[]{a, b});
        }
        return edges;
    }

    static boolean isBipartite(int n, List<int[]> edges) {
        // 建邻接表
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            adj[a].add(b);
            adj[b].add(a);
        }

        int[] color = new int[n + 1]; // 0=未染, 1=红, -1=蓝

        for (int start = 1; start <= n; start++) {
            if (color[start] != 0) continue;
            if (adj[start].isEmpty()) continue; // 孤立节点跳过
            color[start] = 1;
            Queue<Integer> q = new LinkedList<>();
            q.offer(start);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj[u]) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.offer(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

/**
 * 判断是否二分图（BFS 染色）
 */
func isBipartite(n int, edges [][2]int) bool {
	adj := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		adj[i] = []int{}
	}
	for _, e := range edges {
		a, b := e[0], e[1]
		adj[a] = append(adj[a], b)
		adj[b] = append(adj[b], a)
	}

	color := make([]int8, n+1) // 0=未染, 1=红, -1=蓝

	for start := 1; start <= n; start++ {
		if color[start] != 0 {
			continue
		}
		if len(adj[start]) == 0 {
			continue // 孤立节点跳过
		}
		color[start] = 1
		q := []int{start}
		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			for _, v := range adj[u] {
				if color[v] == 0 {
					color[v] = -color[u]
					q = append(q, v)
				} else if color[v] == color[u] {
					return false
				}
			}
		}
	}
	return true
}

/**
 * 解析一行冲突对
 */
func parseConflicts(line string) [][2]int {
	line = strings.TrimSpace(line)
	if line == "" {
		return nil
	}
	parts := strings.Fields(line)
	edges := make([][2]int, 0, len(parts))
	for _, part := range parts {
		nums := strings.Split(part, ",")
		a, _ := strconv.Atoi(nums[0])
		b, _ := strconv.Atoi(nums[1])
		edges = append(edges, [2]int{a, b})
	}
	return edges
}

func main() {
	defer func() {
		if r := recover(); r != nil {
			fmt.Println()
		}
	}()

	scanner := bufio.NewScanner(os.Stdin)

	// 读第一行
	scanner.Scan()
	first := strings.TrimSpace(scanner.Text())
	if first == "" {
		fmt.Println()
		return
	}

	cntParts := strings.Split(first, ",")
	resourceCnt := make([]int, len(cntParts))
	for i, s := range cntParts {
		resourceCnt[i], _ = strconv.Atoi(s)
	}

	results := make([]string, 0, len(resourceCnt))

	for _, n := range resourceCnt {
		scanner.Scan()
		line := strings.TrimSpace(scanner.Text())
		edges := parseConflicts(line)

		// 过滤无效边
		validEdges := make([][2]int, 0)
		for _, e := range edges {
			a, b := e[0], e[1]
			if a >= 1 && a <= n && b >= 1 && b <= n && a != b {
				validEdges = append(validEdges, e)
			}
		}

		if isBipartite(n, validEdges) {
			results = append(results, "1")
		} else {
			results = append(results, "0")
		}
	}

	fmt.Println(strings.Join(results, ","))
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_NODES 10005

/**
 * 简易队列（int）
 */
typedef struct {
    int data[MAX_NODES];
    int head, tail;
} Queue;

void q_init(Queue* q) { q->head = q->tail = 0; }
void q_push(Queue* q, int v) { q->data[q->tail++] = v; }
int q_pop(Queue* q) { return q->data[q->head++]; }
int q_empty(Queue* q) { return q->head == q->tail; }

/**
 * 邻接表（链式前向星）
 */
typedef struct {
    int to[MAX_NODES * 2];
    int next[MAX_NODES * 2];
    int head[MAX_NODES];
    int cnt;
} Graph;

void g_init(Graph* g) {
    g->cnt = 0;
    memset(g->head, -1, sizeof(g->head));
}

void g_add(Graph* g, int u, int v) {
    int idx = g->cnt++;
    g->to[idx] = v;
    g->next[idx] = g->head[u];
    g->head[u] = idx;
}

/**
 * 判断是否二分图（BFS 染色）
 */
int isBipartite(int n, Graph* g) {
    char color[MAX_NODES] = {0}; // 0=未染, 1=红, 2=蓝

    for (int start = 1; start <= n; start++) {
        if (color[start] != 0) continue;
        if (g->head[start] == -1) continue; // 孤立节点跳过
        color[start] = 1;
        Queue q;
        q_init(&q);
        q_push(&q, start);
        while (!q_empty(&q)) {
            int u = q_pop(&q);
            for (int i = g->head[u]; i != -1; i = g->next[i]) {
                int v = g->to[i];
                if (color[v] == 0) {
                    color[v] = 3 - color[u]; // 1->2, 2->1
                    q_push(&q, v);
                } else if (color[v] == color[u]) {
                    return 0;
                }
            }
        }
    }
    return 1;
}

/**
 * 解析一行冲突对并构建图
 */
int parseAndBuild(const char* line, Graph* g) {
    char copy[100000];
    strcpy(copy, line);
    char* token = strtok(copy, " ");
    int cnt = 0;
    while (token != NULL) {
        int a, b;
        if (sscanf(token, "%d,%d", &a, &b) == 2) {
            g_add(g, a, b);
            g_add(g, b, a);
            cnt++;
        }
        token = strtok(NULL, " ");
    }
    return cnt;
}

int main() {
    char line[100000];
    Graph g;

    // 读第一行
    if (fgets(line, sizeof(line), stdin) == NULL) { printf("\n"); return 0; }
    int len = strlen(line);
    if (len > 0 && line[len-1] == '\n') line[len-1] = '\0';

    // 解析 resourceCnt
    int resourceCnt[105], m = 0;
    char* token = strtok(line, ",");
    while (token != NULL) {
        resourceCnt[m++] = atoi(token);
        token = strtok(NULL, ",");
    }

    char result[10000] = {0};

    for (int i = 0; i < m; i++) {
        int n = resourceCnt[i];
        if (fgets(line, sizeof(line), stdin) == NULL) line[0] = '\0';
        len = strlen(line);
        if (len > 0 && line[len-1] == '\n') line[len-1] = '\0';

        g_init(&g);
        parseAndBuild(line, &g);

        int bipartite = isBipartite(n, &g);
        char buf[8];
        sprintf(buf, "%d,", bipartite);
        strcat(result, buf);
    }

    int rlen = strlen(result);
    if (rlen > 0) result[rlen - 1] = '\0';
    printf("%s\n", result);
    return 0;
}

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。