【算法】边双连通分量
【题意&题解】http://blog.****.net/geniusluzh/article/details/6619575 （注意第一份代码是错误的）
一些细节：
1.判断桥只能在树边判断，不能在反向边判断，体现在程序中注释的wrong位置。
2.标记桥要双向标记。
3.第二次dfs的时候记得不走已染色的点，否则会陷入环中。
核心判断：
1.未访问过：取low
2.未访问过：判桥
3.访问过：取dfn
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=,maxm=;
struct edge{int u,v,from;}e[maxm*];
int first[maxn],dfn[maxn],dfsnum,low[maxn],iscut[maxn],cc[maxn],ccnum,n,m,tot,degree[maxn];
void insert(int u,int v)
{tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
int tarjan(int x,int fa)
{
dfn[x]=low[x]=++dfsnum;
for(int i=first[x];i;i=e[i].from)
if(e[i].v!=fa)
{
int y=e[i].v;
if(!dfn[y])
{
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])iscut[i]=,iscut[i%?i+:i-]=;
}
else low[x]=min(low[x],dfn[y]);
// if(low[y]<dfn[x])iscut[i]=1,iscut[i%2?i+1:i-1]=1; wrong
}
}
void dfs(int x,int fa)
{
cc[x]=ccnum;
for(int i=first[x];i;i=e[i].from)
if(e[i].v!=fa&&!iscut[i]&&!cc[e[i].v])dfs(e[i].v,x);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
insert(v,u);
}
for(int i=;i<=n;i++)if(!dfn[i])tarjan(i,-);
// for(int i=1;i<=tot;i++)printf("iscut[%d]%d u=%d v=%d\n",i,iscut[i],e[i].u,e[i].v);
for(int i=;i<=n;i++)
if(!cc[i])
{
ccnum++;
dfs(i,-);
}
int ans=;
for(int i=;i<=tot;i++)
if(cc[e[i].u]!=cc[e[i].v])
{
degree[cc[e[i].u]]++;
degree[cc[e[i].v]]++;
// printf("%d %d\n",cc[e[i].u],cc[e[i].v]);
}
// printf("ccnum=%d\n",ccnum);
for(int i=;i<=ccnum;i++)
if(degree[i]==)ans++;
printf("%d",(ans+)/);
return ;
}