2016-09-14

HDU 3671 Boonie and Clyde【无向图割点】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3671

题意：

给定无向图，去掉两个点，使得图不再连通，问有多少种选择方式？

分析：

枚举每个点，求剩下的图的割点个数。如果枚举的点为割点，则在剩下的图中任选一点都可以，如果非割点，即去掉这个点，剩下的图连通性不变，则只能再选剩下图的割点。这样复杂度为$O(n \times m)$，可以一试。
但是情况并没有这么简单= =
如果枚举的点是割点，剩下的图被分成若干部分，这些部分之间的点不再连通。最后我们还要在剩下的部分中再随便去掉一点，但是如果仅有两部分且其中一部分只有一个点，那么去掉这个点之后相当于只剩下了一部分，显然此时是这个选择是无解的QAQ
所以我们必须对去掉割点后，剩下图被分为两部分，且至少有一部分仅有一个点剩下的情况进行特判。

代码：

/*************************************************************************
    > File Name: 3671.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/13 23:14:54
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e3 + 5, maxm = 1e4 + 5;
int dfnum;
int low[maxn], dfn[maxn];
struct EDGE{
	int to, next;
	bool flag;
}edge[maxm << 1];
int head[maxn];
int tot;
int cnt;
bool vis[maxn];
void init()
{
	memset(vis, 0, sizeof(vis));
	memset(low, 0, sizeof(low));
	memset(dfn, 0, sizeof(dfn));
	dfnum = 1;//1开始
	cnt = 0;
}
void addedge(int from, int to)
{
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}
int num;
void dfs(int u, int pa, int k)
{
	int child = 0;
    dfn[u] = low[u] = dfnum++;
    num++;
	for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
		if(v == k || v == pa) continue;
		if(!dfn[v]){
			child++;
            dfs(v, u, k);
            low[u] = min(low[u], low[v]);
			if(pa == -1 && child > 1){
				if(!vis[u]) cnt++;
				vis[u] = true;
			}
            if(pa != -1 && low[v] >= dfn[u]){
				if(!vis[u]) cnt++;
				vis[u] = true;
			}
        }else{
            low[u] = min(low[u], dfn[v]);
        }
	}
}
int main (void)
{	
	int n, m;
	int kas = 1;
	while(~scanf("%d%d", &n, &m) && (n + m)){
		int u, v;
		memset(head, -1, sizeof(head));
		tot = 0;
		for(int i = 0; i < m; ++i){
			scanf("%d%d", &u, &v);
			addedge(u, v);
			addedge(v, u);
		}
		int ans = 0;
		for(int i = 1; i <= n; ++i){
			init();
			int cntt = 0, t = 0;
			for(int j = 1; j <= n; j++){
				if(j == i || dfn[j]) continue;
				cntt++;
				num = 0;
				dfs(j, -1, i);
				if(num == 1) t++;
			}
			if(cntt == 1) ans += cnt;
			else if(cntt == 2 && t == 1) ans += n - 2;
			else if(cntt == 2 && t == 0) ans += n - 1;
			else if(cntt > 2) ans += n - 1;
		}
		printf("Case %d: %d\n", kas++, ans / 2);
	}
	return 0;
}