首页 > 代码库 > POJ 2793 Cactus
POJ 2793 Cactus
题意:
给你一幅无向图 计算它有多少生成子图是仙人掌 如果它本身不是仙人掌输出0
思路:
无向图的仙人掌是一个连通图且一条边最多在一个环上
对于这道题 需要区分“生成子图”和“导出子图”的概念
生成子图:包含G的所有顶点V和其中一些边的子图
导出子图:选择G中一些点组成集合V‘,将E中所有两端点在V‘中的边全部找出形成的子图叫点导出子图;选择G中一些边组成集合E‘,将V中所有与E‘中的边有关系的点全部找出形成的子图叫边导出子图。
那么这道题就是说你要扔掉一些边 使图还是仙人掌 问方案数
易知扔掉的边必定是环上的边 而且由于原图是仙人掌 所以每个环只能扔1条边或不扔
那么总方案数其实就是所有的环中的边数加一后的乘积 由于最后数字很大所以要用高精度
PS:
其实我不会java… 所以代码很丑… 有能改进的地方还望各位指出 感激不尽
代码:
import java.io.*; import java.util.*; import java.math.*; public class Main { class edge { int v, next; boolean flag; edge(int v, int next) { this.v = v; this.next = next; this.flag = false; } } edge[] ed = new edge[2000001]; int[] head = new int[20001]; int[] dfn = new int[20001]; int[] low = new int[20001]; int[] st = new int[2000001]; int tot, idx, top; BigInteger res; public void tarjan(int u, int fa) { int i, j, v, f = 0; dfn[u] = low[u] = ++idx; for (i = head[u]; i != -1; i = ed[i].next) { v = ed[i].v; if (ed[i].flag) continue; ed[i].flag = ed[i ^ 1].flag = true; st[++top] = i; if (dfn[v] == -1) { tarjan(v, u); low[u] = min(low[u], low[v]); if (dfn[u] <= low[v]) { int num = 0; do { j = st[top--]; num++; } while (i != j); if (num > 1) num++; res = res.multiply(new BigInteger(num + "")); } } else low[u] = min(low[u], dfn[v]); if (low[v] < dfn[u]) f++; } if (f > 1) res = BigInteger.ZERO; } public static int min(int i, int j) { if (i < j) return i; return j; } public void solve(int n) { idx = top = 0; res = BigInteger.ONE; tarjan(1, 1); for (int i = 1; i <= n; i++) { if (dfn[i] == -1) { res = BigInteger.ZERO; break; } } } public void run() { Scanner cin = new Scanner(System.in); int n, m, i, j, k, u, v; while (cin.hasNext()) { n = cin.nextInt(); m = cin.nextInt(); tot = 0; for (i = 1; i <= n; i++) { dfn[i] = -1; head[i] = -1; } for (i = 1; i <= m; i++) { k = cin.nextInt(); u = cin.nextInt(); for (j = 2; j <= k; j++) { v = cin.nextInt(); ed[tot] = new edge(v, head[u]); head[u] = tot++; ed[tot] = new edge(u, head[v]); head[v] = tot++; u = v; } } solve(n); System.out.println(res); } cin.close(); } public static void main(String[] args) { new Main().run(); } }
POJ 2793 Cactus
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。