http://acm.hdu.edu.cn/showproblem.php?pid=3671
给出一幅无向图，询问有多少种移除点对的方案使得剩下的连通分量个数大于1.
和上一题差不多的思路直接做n次tarjin即可。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define LL long long
#define pb push_back
const int maxn=;
vector<int>g[maxn];
int dfn[maxn],low[maxn],sub[maxn],root,sum,ban;
bool vis[maxn];
void dfs(int u){
dfn[u]=low[u]=sum++;
vis[u]=;
int son=;
for(int i=;i<g[u].size();++i){
int v=g[u][i];
if(v==ban) continue;
if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
else{
dfs(v);
if(u==root)son++;
else{
if(low[v]>=dfn[u])sub[u]++;
}
low[u]=min(low[u],low[v]);
}
}
if(u==root)sub[u]=son;
else sub[u]++;
}
int main(){
int n,m,cas=,i,j,u,v;
while(scanf("%d%d",&n,&m)==){
if(n==&&m==)break;
for(i=;i<=n;++i)g[i].clear();
while(m--){
scanf("%d%d",&u,&v);
g[u].pb(v);
g[v].pb(u);
}
int ans=;
for(i=;i<=n;++i){
int p=;
ban=i,sum=;
memset(vis,,sizeof(vis));
memset(sub,,sizeof(sub));
for(j=;j<=n;++j){
if(j==ban || vis[j]) continue;
root=j;
p++;
dfs(j);
}
//cout<<"p="<<p<<endl;
for(j=i+;j<=n;++j){
if(sub[j]+p->=)ans++;
}
}
printf("Case %d: %d\n",++cas,ans);
}
return ;
}