本文主要是介绍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 + ""));}} elselow[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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
