题意：给定n个点m条边。要使任意两个点可以通过两条严格不同的路径到达。即边不能重复，点可以重复。求需要添加的最小边数
题目就是要求使这个图成为边双连通分量所需添加的最小边数。
我的做法：
将边双连通分量相关的点缩点。然后求出度为1的个数=num。答案就是(num+1)/2或者说是num/2+num%2
理由：度为1的肯定是叶子节点或者根节点。将叶子节点两两配对。如果是奇数的话就任意与一个节点配对成边即可。
我在做边双连通分量缩点的过程异常麻烦。
首先我求出桥，然后删掉这些桥。将连通块缩点(这些连通块是边双连通分量)。然后再计算度数。。写的很多。感觉很麻烦。肯定有更简短的代码。。
---------2014/7/11 在下面还有一个代码 修改过后的。。写法比前面这个简便多了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 5010
vector <int> e[MAXN];
vector <int> e1[MAXN];
vector <int> e2[MAXN];
int dfn[MAXN],low[MAXN],pre[MAXN],n,m;
int times=0,tot=0;
int du[MAXN];
void tarjan_3(int u){
dfn[u]=low[u]=++times;
for(int i=0;i<(int)e[u].size();i++){
int v=e[u][i];
if(!dfn[v]){
pre[v]=u;
tarjan_3(v);
low[u]=min(low[u],low[v]);
}
else if(pre[u]!=v){
low[u]=min(low[u],dfn[v]);
}
}
}
int vis[MAXN],tots;
void bfs(int u){
vis[u]=++tots;
queue <int> q;
q.push(u);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<(int)e2[now].size();i++){
int next=e2[now][i];
if(vis[next])continue;
vis[next]=vis[now];
q.push(next);
}
}
}
bool check(int u,int v){
if(e1[u].empty())return true;
for(int i=0;i<(int)e1[u].size();i++){
int v1=e1[u][i];
if(v1==v)return false;
}
return true;
}
char has[MAXN];
void bfs1(int x){
queue <int> q;
q.push(x);
has[x]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<(int)e1[now].size();i++){
int next=e1[now][i];
if(has[next])continue;
has[next]=1;
++du[now];
++du[next];
q.push(next);
}
}
}
void solve(){
tots=times=tot=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan_3(i);
for(int i=1;i<=n;i++){
if(pre[i]>0&&dfn[pre[i]]<low[i]){
e1[pre[i]].push_back(i);
e1[i].push_back(pre[i]);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<(int)e[i].size();j++){
int v=e[i][j];
if(check(i,v)){
e2[i].push_back(v);
e2[v].push_back(i);
}
}
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
if(!vis[i]){
bfs(i);
}
}
memset(du,0,sizeof(du));
for(int i=0;i<n+10;i++)e1[i].clear();
for(int i=1;i<=n;i++){
for(int j=0;j<(int)e[i].size();j++){
int v=e[i][j];
if(vis[i]==vis[v])continue;
e1[vis[i]].push_back(vis[v]);
e1[vis[v]].push_back(vis[i]);
}
}
memset(has,0,sizeof(has));
for(int i=1;i<=tots;i++)
if(!has[i])bfs1(i);
int cnt=0;
for(int i=1;i<=tots;i++){
if(du[i]==1)++cnt;
}
printf("%d\n",(cnt+1)/2);
return ;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<n+10;i++)e[i].clear();
for(int i=0;i<n+10;i++)e1[i].clear();
for(int i=0;i<n+10;i++)e2[i].clear();
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
solve();
}
return 0;
}
|
代码二:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 5010
struct Edge
{
int to,next;
bool vis,bge;
}edge[MAXN*2];
int dfn[MAXN],low[MAXN],pre[MAXN];
int sta[MAXN],bleg[MAXN];
int times,n,m,top;
int tot,head[MAXN];
void Add(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
edge[tot].vis=false;
edge[tot].bge=false;
head[u]=tot++;
}
void tarjan_3(int u){
dfn[u]=low[u]=++times;
sta[++top]=u;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(edge[i].vis)continue;
edge[i].vis=edge[i^1].vis=true;
if(!dfn[v]){
pre[v]=u;
tarjan_3(v);
low[u]=min(low[u],low[v]);
}
else if(!bleg[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
bleg[0]++;
do{
bleg[sta[top]]=bleg[0];
}while(sta[top--]!=u);
bleg[u]=bleg[0];
}
}
int du[MAXN];
void solve(){
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(pre,0,sizeof(pre));
memset(bleg,0,sizeof(bleg));
memset(du,0,sizeof(du));
top=times=0;
for(int i=1;i<=n;i++)
if(!dfn[i]){
tarjan_3(i);
}
for(int i=0;i<tot;i++){
if(edge[i].bge)continue;
int u=edge[i].to;
int v=edge[i^1].to;
if(pre[v]==u&&dfn[u]<low[v]){
edge[i].bge=edge[i^1].bge=true;
}
}
for(int i=1;i<=n;i++){
for(int j=head[i];j!=-1;j=edge[j].next){
int v=edge[j].to;
if(bleg[i]==bleg[v])continue;
++du[bleg[i]];
}
}
int cnt=0;
for(int i=1;i<=bleg[0];i++){
if(du[i]==1)++cnt;
}
printf("%d\n",(cnt+1)/2);
}
int main()
{
while(~scanf("%d%d",&n,&m)){
tot=0;
memset(head,-1,sizeof(head));
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
Add(x,y);
Add(y,x);
}
solve();
}
return 0;
}
|
