北京网站设计公司兴田德润简介wordpress摘要

北京网站设计公司兴田德润简介,wordpress摘要,广告代理商是什么,直装模板下载(200分)- 无向图染色#xff08;Java JS Python#xff09;题目描述给一个无向图染色#xff0c;可以填红黑两种颜色#xff0c;必须保证相邻两个节点不能同时为红色#xff0c;输出有多少种不同的染色方案#xff1f;输入描述第一行输入M(图中节点数) N(边数…(200分)- 无向图染色Java JS Python题目描述给一个无向图染色可以填红黑两种颜色必须保证相邻两个节点不能同时为红色输出有多少种不同的染色方案输入描述第一行输入M(图中节点数) N(边数)后续N行格式为V1 V2表示一个V1到V2的边。数据范围1 M 15,0 N M * 3不能保证所有节点都是连通的。输出描述输出一个数字表示染色方案的个数。用例输入4 41 22 43 41 3输出7说明4个节点4条边1号节点和2号节点相连2号节点和4号节点相连3号节点和4号节点相连1号节点和3号节点相连若想必须保证相邻两个节点不能同时为红色总共7种方案。输入3 31 21 32 3输出4说明无输入4 31 22 33 4输出8说明无输入4 31 21 32 3输出8说明无题目解析本题其实就是求解连通图的染色方案目前我想到的最好方式是暴力法即通过回溯算法求解出染红节点的全组合n个数的全组合数量一共有 (2^n) - 1。比如1,2,3的全组合情况有1、2、3、12、13、23、123即 (2^3) - 1 7个。本题中节点一共有m个而1 m 15即最多有 (2^15) - 1 32767 个组合情况这个数量级不算多。 因此暴力法可行。我们需要尝试对组合中的节点进行染红色但是相邻节点不能同时染成红色。因此在求解全组合时还可以进行剪枝优化即判断新加入的节点 是否和 已存在的节点相邻如果相邻则剪枝如果不相邻则继续递归。// 连通图的染色方案数求解 function getDyeCount(arr, m) { // connect用于存放每个节点的相邻节点 const connect {}; for (let [v1, v2] of arr) { connect[v1] ? connect[v1].add(v2) : (connect[v1] new Set([v2])); connect[v2] ? connect[v2].add(v1) : (connect[v2] new Set([v1])); } // 必有一种全黑的染色方案 let count 1; // 求解染红节点的全组合情况 function dfs(m, index, path) { if (path.length m) return; outer: for (let i index; i m; i) { // 如果新加入节点和已有节点相邻则说明新加入节点不能染成红色需要进行剪枝 for (let j 0; j path.length; j) { if (path[j].has(i)) continue outer; } count; path.push(connect[i]); dfs(m, i 1, path); path.pop(); } } // 节点从1开始 dfs(m, 1, []); return count; }本题到此还未结束因为题目中有一句话不能保证所有节点都是连通的这说明什么呢即对应用例4的情况用例4对应的无向图如下此时一共有8种染色方案如下其实就是先求解无向图的各个连通分量比如用例4的无向图就有两个连通分量分别是{4}{123}然后求解各连通分量各自的染色方案比如{4} 有2种染色方案{123} 有4种染色方案那么总染色方案数目就是2*48种因此本题还考察了连通分量的求解。连通分量的求解可以使用并查集但是本题实现上可以取巧即不需要使用并查集去求解连通分量而是完全依赖于暴力因为不管节点是否在一个连通分量中还是不在一个连通分量中他们的染色都要满足相邻节点不能同时为红色因此处于两个连通分量中的节点必然不相连则必然可以同时染红因此直接用前面求染红节点组合就可以不需要用并查集。补充一个边界用例情况4 32 32 43 4输出应该是8但是节点1和任何其他节点不相连也没有在边因此下面代码统计connect时即统计每个节点的相邻节点必然统计不到节点1即connect[1] 的值为null因此后续获取节点1的相邻节点时会得到null此时我们应该要特殊处理null。JavaScript算法源码直接利用节点间相邻关系暴力枚举所有染色方案。该方案实现上更简单但是性能没有基于并查集求出各连通分量后分别求解染色方案的好。/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines []; let m, n; rl.on(line, (line) { lines.push(line); if (lines.length 1) { [m, n] lines[0].split( ).map(Number); } if (n ! undefined lines.length n 1) { const arr lines.slice(1).map((line) line.split( ).map(Number)); console.log(getResult(arr, m)); lines.length 0; } }); /** * * param {*} arr 边即[v1, v2] * param {*} m 点数量 */ function getResult(arr, m) { // connect用于存放每个节点的相邻节点 const connect {}; for (let [v1, v2] of arr) { connect[v1] ? connect[v1].add(v2) : (connect[v1] new Set([v2])); connect[v2] ? connect[v2].add(v1) : (connect[v2] new Set([v1])); } // 必有一种全黑的染色方案 let count 1; // 求解染红节点的全组合情况 function dfs(m, index, path) { if (path.length m) return; outer: for (let i index; i m; i) { // 如果新加入节点和已有节点相邻则说明新加入节点不能染成红色需要进行剪枝 for (let j 0; j path.length; j) { if (path[j].has(i)) continue outer; } count; if (connect[i] ! undefined) { path.push(connect[i]); dfs(m, i 1, path); path.pop(); } else { dfs(m, i 1, path); } } } // 节点从1开始 dfs(m, 1, []); return count; }Java算法源码直接利用节点间相邻关系暴力枚举所有染色方案。该方案实现上更简单但是性能没有基于并查集求出各连通分量后分别求解染色方案的好。import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); int[][] edges new int[n][2]; for (int i 0; i n; i) { edges[i][0] sc.nextInt(); edges[i][1] sc.nextInt(); } System.out.println(getResult(edges, m)); } /** * param edges 边即[v1, v2] * param m 点数量 * return */ public static int getResult(int[][] edges, int m) { // connect用于存放每个节点的相邻节点 HashMapInteger, HashSetInteger connect new HashMap(); for (int[] edge : edges) { connect.putIfAbsent(edge[0], new HashSet()); connect.get(edge[0]).add(edge[1]); connect.putIfAbsent(edge[1], new HashSet()); connect.get(edge[1]).add(edge[0]); } // 节点从index1开始必有count1个的全黑染色方案 return dfs(connect, m, 1, 1, new LinkedList()); } // 该方法用于求解给定多个节点染红的全组合数 public static int dfs( HashMapInteger, HashSetInteger connect, int m, int index, int count, LinkedListHashSetInteger path) { if (path.size() m) return count; outer: for (int i index; i m; i) { // 如果新加入节点i和已有节点j相邻则说明新加入节点不能染成红色需要进行剪枝 for (HashSetInteger p : path) { if (p.contains(i)) continue outer; } count; if (connect.containsKey(i)) { path.addLast(connect.get(i)); count dfs(connect, m, i 1, count, path); path.removeLast(); } else { count dfs(connect, m, i 1, count, path); } } return count; } }Python算法源码# 输入获取 m, n map(int, input().split()) arr [list(map(int, input().split())) for i in range(n)] # 算法入口 def getResult(arr, m): :param arr: 边即[v1, v2] :param m: 点数量 :return: 染色方案数 # connect用于存放每个节点的相邻节点 connect {} for v1, v2 in arr: if connect.get(v1) is None: connect[v1] set() connect[v1].add(v2) if connect.get(v2) is None: connect[v2] set() connect[v2].add(v1) # 节点从1开始 return dfs(m, 1, [], 1, connect) # 求解染红节点的全组合情况 def dfs(m, index, path, count, connect): :param m: 点数量点从1计数 :param index: 当前第几个点 :param path: 保存点的容器 :param count: 染色方案数量 :param connect: 每个节点的相邻节点 :return: 染色方案数量 if len(path) m: return count flag False for i in range(index, m 1): # 如果新加入节点和已有节点相邻则说明新加入节点不能染成红色需要进行剪枝 for p in path: if i in p: flag True break if flag: flag False continue count 1 if connect.get(i) is not None: path.append(connect.get(i)) count dfs(m, i 1, path, count, connect) path.pop() else: count dfs(m, i 1, path, count, connect) return count # 算法调用 print(getResult(arr, m))