题意：
给你一个无向图，要求把所有无向边改成有向边，并且添加最少的有向边，使得新的有向图强联通。
分析：
这题的解法还是很好想的。先用边双联通分量缩点，然后找新图中入度为0和为1的点，入度为0则ans+2，为1则ans+1，最后输出（ans+1）/2。
注意，如果原图本来就强联通，答案为0不是1。
在这里主要说说打边双联通的注意事项。（一开始觉得是跟点双连通差不多的，调试的时候才发现很容易疏忽导致BUG很多啊）
1、如果有重边，则那条就不是割边了，我们很容易向上重走树枝边的反向边导致程序认为这是返祖边。在点双连通中判断一下是不是父亲即可，但边双联通不行。（因为重边对点双连通无影响，但对边双联通有影响）所以要做一个标记，走树枝边的时候把反向边也标记一下。
2、stack中的剩余元素最后要记得pop出来。
3、图不一定联通，要for一遍再dfs。
4、发现(x,y)为割边的时候，(dfn[x]<dfn[y])，边双联通分量是算到y而不是x。（跟点双连通有一点不一样）
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define Maxn 1010 struct node
{
int x,y,next;
bool vis;
}t[*Maxn*Maxn];int len; int first[Maxn],n,m;
int dfn[Maxn],low[Maxn],cnt;
int cc[Maxn],cl,sum[Maxn];
stack<int > s; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;t[len].vis=;
t[len].next=first[x];first[x]=len;
} int mymin(int x,int y) {return x<y?x:y;} void ffind(int x)
{
dfn[x]=low[x]=++cnt;
s.push(x);
for(int i=first[x];i;i=t[i].next) if(!t[i].vis)
{
int y=t[i].y;
t[i].vis=;t[i+(i%==?:-)].vis=;
if(!dfn[y])
{
ffind(y);
low[x]=mymin(low[x],low[y]);
if(low[y]>dfn[x])
{
cl++;
while(!s.empty())
{
int z=s.top();
s.pop();
cc[z]=cl;
if(z==y) break;
}
}
}
else low[x]=mymin(low[x],dfn[y]);
}
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
len=;cnt=;cl=;
memset(first,,sizeof(first));
memset(dfn,,sizeof(dfn));
memset(cc,,sizeof(cc));
memset(sum,,sizeof(sum));
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
if(!s.empty()) s.pop();
for(int i=;i<=n;i++)if(!dfn[i])
{
ffind(i);
if(!s.empty())
{
cl++;
while(!s.empty())
{
cc[s.top()]=cl;
s.pop();
}
}
}
if(cl==) {printf("0\n");continue;} int ans=;
for(int i=;i<=len;i++)
{
if(cc[t[i].x]==cc[t[i].y]) continue;
sum[cc[t[i].x]]++;
}
for(int i=;i<=cl;i++) if(sum[i]==) ans++;
else if(sum[i]==) ans+=;
printf("%d\n",(ans+)/);
}
return ;
}
[uva10972]
2016-03-23 13:54:57