http://poj.org/problem?id=3352
有重边的话重边就不被包含在双连通里了
割点不一定连着割边,因为这个图不一定是点连通,所以可能出现反而多增加了双连通分量数的可能
必须要用割边的思路来看
#include <cstdio>
#include <vector >
using namespace std;
const int maxn=1001;
vector<int >G[maxn]; int low[maxn],dfn[maxn];
bool vis[maxn]; int dg[maxn]; int dep,cnt;
void dfs(int s,int f){
low[s]=dfn[s]=++dep;
vis[s]=true;
for(int i=0;i<G[s].size();i++){
int t=G[s][i];
if(t==f)continue;
if(!vis[t]){
dfs(t,s);
low[s]=min(low[s],low[t]);
}
else low[s]=min(low[s],dfn[t]);
}
}
int n,r;
int main(){
scanf("%d%d",&n,&r);
int f,t;
while(r--){scanf("%d%d",&f,&t);G[f].push_back(t);G[t].push_back(f);}
dfs(1,-1); for(int i=1;i<=n;i++){
for(int j=0;j<G[i].size();j++){
if(low[i]!=low[G[i][j]])dg[low[i]]++;
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(dg[i]==1)ans++;
}
ans=(ans+1)/2;
printf("%d\n",ans);
return 0;
}