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();
	}
}