企业官网建设流程全解析

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

示例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,2,3,4资源，conflicts[0]=[(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
输入：[1,2,4],[[],[(1, 2)],[(1,2),(2,3),(3,4),(4,1)]]
输出：[1,1,1]
说明：第1组任务没有冲突，可以划分。
第2 组任务中资源1和资源2分别放入不同资源池即可。
第3组任务形成偶数环，可以被两个资源池隔离。
示例3
输入：[3,4],[[(1,1)],[(1,2),(2,3),(3,1)] ]输出：[0,0]
说明：第1组任务中资源1与自己冲突，无法划分。
第2组任务中资源1、2、3形成奇数环，无法只用两个资源池隔离。

以下是针对题目要求的完美实现，分别使用C、C++、JavaScript、Java、Go和Python语言编写。每个实现都包含一个主函数或方法，用于处理输入（resourceCount数组和conflicts数组），并返回结果数组（每个元素表示对应任务组是否可划分）。代码使用BFS算法检测二分图（即资源单元是否可以划分到两个资源池），并处理自环和互斥关系。

C 语言实现

#include <stdlib.h> #include <stdbool.h> bool is_bipartite(int n, int** edges, int edges_count) { for (int i = 0; i < edges_count; i++) { int u = edges[i][0]; int v = edges[i][1]; if (u == v) { return false; } } int** graph = (int**)malloc((n+1) * sizeof(int*)); int* sizes = (int*)calloc(n+1, sizeof(int)); for (int i = 0; i < edges_count; i++) { int u = edges[i][0]; int v = edges[i][1]; sizes[u]++; sizes[v]++; } for (int i = 1; i <= n; i++) { graph[i] = (int*)malloc(sizes[i] * sizeof(int)); } for (int i = 1; i <= n; i++) { sizes[i] = 0; } for (int i = 0; i < edges_count; i++) { int u = edges[i][0]; int v = edges[i][1]; graph[u][sizes[u]++] = v; graph[v][sizes[v]++] = u; } int* color = (int*)malloc((n+1) * sizeof(int)); for (int i = 1; i <= n; i++) { color[i] = -1; } int* queue = (int*)malloc(n * sizeof(int)); bool bipartite = true; for (int i = 1; i <= n; i++) { if (color[i] == -1) { int front = 0, rear = 0; queue[rear++] = i; color[i] = 0; while (front < rear) { int u = queue[front++]; for (int j = 0; j < sizes[u]; j++) { int v = graph[u][j]; if (color[v] == -1) { color[v] = 1 - color[u]; queue[rear++] = v; } else if (color[v] == color[u]) { bipartite = false; break; } } if (!bipartite) { break; } } if (!bipartite) { break; } } } free(color); free(queue); for (int i = 1; i <= n; i++) { free(graph[i]); } free(graph); free(sizes); return bipartite; } int* can_divide(int* resourceCount, int resourceCountSize, int*** conflicts, int* conflictsSize, int* conflictsColSize) { int* results = (int*)malloc(resourceCountSize * sizeof(int)); for (int i = 0; i < resourceCountSize; i++) { int n = resourceCount[i]; int edges_count = conflictsColSize[i]; int** edges = conflicts[i]; bool bipartite = is_bipartite(n, edges, edges_count); results[i] = bipartite ? 1 : 0; } return results; }

C++ 语言实现

#include <vector> #include <queue> using namespace std; bool is_bipartite(int n, vector<vector<int>>& edges) { for (auto& edge : edges) { int u = edge[0]; int v = edge[1]; if (u == v) { return false; } } vector<vector<int>> graph(n+1); for (auto& edge : edges) { int u = edge[0]; int v = edge[1]; graph[u].push_back(v); graph[v].push_back(u); } vector<int> color(n+1, -1); for (int i = 1; i <= n; i++) { if (color[i] == -1) { queue<int> q; q.push(i); color[i] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); } else if (color[v] == color[u]) { return false; } } } } } return true; } vector<int> can_divide(vector<int>& resourceCount, vector<vector<vector<int>>>& conflicts) { vector<int> results; for (int i = 0; i < resourceCount.size(); i++) { int n = resourceCount[i]; auto& edges = conflicts[i]; if (is_bipartite(n, edges)) { results.push_back(1); } else { results.push_back(0); } } return results; }

JavaScript 语言实现

function isBipartite(n, edges) { for (let edge of edges) { let [u, v] = edge; if (u === v) { return false; } } let graph = Array.from({ length: n + 1 }, () => []); for (let edge of edges) { let [u, v] = edge; graph[u].push(v); graph[v].push(u); } let color = Array(n + 1).fill(-1); for (let i = 1; i <= n; i++) { if (color[i] === -1) { let queue = [i]; color[i] = 0; while (queue.length > 0) { let u = queue.shift(); for (let v of graph[u]) { if (color[v] === -1) { color[v] = 1 - color[u]; queue.push(v); } else if (color[v] === color[u]) { return false; } } } } } return true; } function canDivide(resourceCount, conflicts) { let results = []; for (let i = 0; i < resourceCount.length; i++) { let n = resourceCount[i]; let edges = conflicts[i]; results.push(isBipartite(n, edges) ? 1 : 0); } return results; }

Java 语言实现

import java.util.*; public class Solution { public static boolean isBipartite(int n, List<int[]> edges) { for (int[] edge : edges) { int u = edge[0], v = edge[1]; if (u == v) { return false; } } List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int[] edge : edges) { int u = edge[0], v = edge[1]; graph.get(u).add(v); graph.get(v).add(u); } int[] color = new int[n + 1]; Arrays.fill(color, -1); for (int i = 1; i <= n; i++) { if (color[i] == -1) { Queue<Integer> queue = new LinkedList<>(); queue.add(i); color[i] = 0; while (!queue.isEmpty()) { int u = queue.poll(); for (int v : graph.get(u)) { if (color[v] == -1) { color[v] = 1 - color[u]; queue.add(v); } else if (color[v] == color[u]) { return false; } } } } } return true; } public static int[] canDivide(int[] resourceCount, List<List<int[]>> conflicts) { int[] results = new int[resourceCount.length]; for (int i = 0; i < resourceCount.length; i++) { int n = resourceCount[i]; List<int[]> edges = conflicts.get(i); results[i] = isBipartite(n, edges) ? 1 : 0; } return results; } }

Go 语言实现

package main func isBipartite(n int, edges [][2]int) bool { for _, edge := range edges { u, v := edge[0], edge[1] if u == v { return false } } graph := make([][]int, n+1) for i := range graph { graph[i] = make([]int, 0) } for _, edge := range edges { u, v := edge[0], edge[1] graph[u] = append(graph[u], v) graph[v] = append(graph[v], u) } color := make([]int, n+1) for i := range color { color[i] = -1 } for i := 1; i <= n; i++ { if color[i] == -1 { queue := []int{i} color[i] = 0 for len(queue) > 0 { u := queue[0] queue = queue[1:] for _, v := range graph[u] { if color[v] == -1 { color[v] = 1 - color[u] queue = append(queue, v) } else if color[v] == color[u] { return false } } } } } return true } func canDivide(resourceCount []int, conflicts [][][2]int) []int { results := make([]int, len(resourceCount)) for i, n := range resourceCount { edges := conflicts[i] if isBipartite(n, edges) { results[i] = 1 } else { results[i] = 0 } } return results }

Python 语言实现

def can_divide(resourceCount, conflicts): results = [] for i in range(len(resourceCount)): n = resourceCount[i] edges = conflicts[i] for edge in edges: u, v = edge if u == v: results.append(0) break else: graph = [[] for _ in range(n+1)] for edge in edges: u, v = edge graph[u].append(v) graph[v].append(u) color = [-1] * (n+1) bipartite = True for node in range(1, n+1): if color[node] == -1: queue = [node] color[node] = 0 while queue: u = queue.pop(0) for v in graph[u]: if color[v] == -1: color[v] = 1 - color[u] queue.append(v) elif color[v] == color[u]: bipartite = False break if not bipartite: break if not bipartite: break results.append(1 if bipartite else 0) return results