@[双连通分量]
题意：
有一个 n 个点 m 条边的无向图，问至少添加几条边，能让该图任意缺少一条边后还能相互连通。
双连通分量定义：
在无向连通图中，如果删除该图的任何一个结点都不能改变该图的连通性，则该图为双连通的无向图。一个连通的无向图是双连通的，当且仅当它没有关节点（这里面节点可换成边：分点双连通分量 ，分边双连通分量）。
思路：
首先缩点成树；
与强连通分量缩点有所不同：记录父节点 ，不返回父节点 （意味着一条边只能从任意方向走一次） ；如果已经走过 ，直接可更新low值（目前理解：若这个点 B 已经走过，出栈后还能再次通过 A 访问到，说明从 B 也能访问到 A ，所以不需要是否在栈中的判断，在强连通分量中，因为是单向，所以只能从 A -> B ,需要是否在栈中的判断）。
试了一下加上栈的判断也对：因为访问B的时候直接就通过B 把 A 访问了，不会等到 A 去访问 B 。
缩点成树之后：
统计有 ans 个双连通分量只有一条边且只与一个双连通分量相连,（ans+1)/2 就是至少要加的边数
撸代码
#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1010
struct node
{
int to,nex;
} edge[N*2];
int cost[N],dfn[N],low[N],belong[N],head[N];
bool instack[N];
int in[N];
int cnt,cir,index;
stack<int>s;
vector<int>point[N];
void init()
{
cnt=0;
cir=0;
index=0;
while(!s.empty())
s.pop();
for(int i=0; i<N; i++)
{
point[i].clear();
head[i]=-1;
in[i]=0;
instack[i]=false;
dfn[i]=0;
low[i]=0;
belong[i]=0;
}
}
void addEdge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].nex=head[u];
head[u]=cnt++;
}
/*求双连通分量*/
void Tarjan(int u,int fa)
{
dfn[u]=low[u]=++index;
instack[u]=true;
s.push(u);
for(int i=head[u]; i!=-1; i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa)
continue;
if(!dfn[v])
{
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else //if(instack[v])
{/*走过且不在栈中*/
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
int node;
++cir;
do
{
node=s.top();
s.pop();
belong[node]=cir;
point[cir].push_back(node);
instack[node]=false;
}
while(node!=u);
}
return ;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
init();
int a,b;
for(int i=0; i<m; i++)
{
scanf("%d%d",&a,&b);
addEdge(a,b);
addEdge(b,a);
}
for(int i=1; i<=n; i++)
if(!dfn[i])
Tarjan(i,i);
/*直到每个点所属的强连通分量*/
// printf("cir = %d
",cir);
// for(int i=1;i<=cir;i++)
// {
// printf("cnt [%d]:",i);
// for(int j=0;j<point[i].size();j++)
// printf("%d ",point[i][j]);
// printf("
");
// }
for(int i=1; i<=n; i++)
{
for(int j=head[i]; j!=-1; j=edge[j].nex)
{
/*!根据统计边 统计连通分量之间的度*/
a=belong[i];
b=belong[edge[j].to];
if(a!=b)
{
in[a]++;
in[b]++;
}
}
}
int ans=0;
for(int i=1; i<=cir; i++)
{
if(in[i]==2)
ans++;
}
printf("%d
",(ans+1)/2);
}
return 0;
}