网站建设 开题报告seo专员的工作内容

题意：求最少添加多少条边可变无桥的连通图。

思路：求出所有的双连通分量（块），然后进行缩点。所求为缩点后的图的叶子数量加1，再除以2。要点：属于同一双连通分支的点的low值必相同。求双连通分量时可以不用dfn数组。

注意：题目中有重边，可以用邻接矩阵判断一下重；存在临界表时判断一下也不会超时。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 5005
#define M 10005
int n,m,top;
bool flag[N][N];
int low[N],first[N];
int id,d[N];
struct edge{int y,next;
}e[M<<1];
void add(int x,int y){e[top].y = y;e[top].next = first[x];first[x] = top++;
}
void tarjan(int x,int fa){int i;low[x] = ++id;for(i = first[x];i!=-1;i=e[i].next){if(e[i].y == fa)continue;if(low[e[i].y] == -1)tarjan(e[i].y,x);low[x] = min(low[x] , low[e[i].y]);}
}
int main(){int i,j,a,b,res=0;top = id = 0;memset(first, -1, sizeof(first));memset(d, 0, sizeof(d));memset(low, -1, sizeof(low));scanf("%d %d",&n,&m);for(i = 1;i<=m;i++){scanf("%d %d",&a,&b);if(!flag[a][b]){add(a,b);add(b,a);flag[a][b] = flag[b][a] = true;}}tarjan(1,-1);for(a = 1;a<=n;a++)for(j = first[a];j!=-1;j=e[j].next){b = e[j].y;if(low[a] != low[b])d[low[a]]++;}for(i = 1;i<=n;i++)if(d[i] == 1)res++;printf("%d\n",(res+1)/2);return 0;
}

int test(int x,int y){int i;for(i = first[x];i!=-1;i=e[i].next)if(e[i].y == y)return 1;return 0;
}