//给一个连通无向图//定义去除一条边即能使得一个点与其他点不连通的边为桥//问加一条边后最少有几个桥//用tarjan对该无向图进行缩点//由于该无向图是一个连通图，所以缩点后其为一棵树，数的节点个数为num//该树的所有边都是桥//要加一条边使得桥最少，只需要将这条边加在这棵树的直径r的两个端点上//即最终的最少桥的个数为num-1-r#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<map>#pragma comment(linker, "/STACK:102400000,102400000")using namespace std ;const int maxm = 1000100 ;const int maxn = 200010 ;struct Edge{ int v ;int u ; int next ;}edge[maxm*2];int head[maxn] ;int nedge ;vector<int> vec[maxn] ;void addedge(int u , int v){ edge[nedge].v = v ; edge[nedge].u = u ; edge[nedge].next = head[u] ; head[u] = nedge++ ;}int dfn[maxn] , low[maxn] , belong[maxn] ;int step , num ,top;int n , m ;int ans ;int stack[maxn] , isstack[maxn] , vis[maxm*2];int dp[maxn][2] ;void init(){ memset(dfn , 0 ,sizeof(dfn)) ; memset(isstack , 0 ,sizeof(isstack)) ; memset(head , -1 , sizeof(head)) ; memset(vis , 0 , sizeof(vis)) ; memset(dp , 0 , sizeof(dp)) ; for(int i = 0 ;i < maxn;i++) vec[i].clear() ; step = num = nedge = top = 0 ;}void tarjan(int u){ stack[++top] = u ; isstack[u] = 1; dfn[u] = low[u] = ++step; for(int i = head[u] ;i != -1 ; i = edge[i].next) { if(vis[i])continue ; vis[i^1] = vis[i] = 1; //遍历完一条边将该边和其反向边标记 int v = edge[i].v ; if(!dfn[v]) { tarjan(v) ; low[u] = min(low[u] , low[v]) ; } else if(isstack[v]) low[u] = min(low[u] , dfn[v]) ; } if(low[u] == dfn[u]) { num++ ; int v = 0; while(u!=v) { v = stack[top–] ; belong[v] = num ; isstack[v] = 1; } }}void build_tree(){ int sum = 0 ; for(int i = 0;i < 2*m;i+=2) { int v = belong[edge[i].v]; int u = belong[edge[i].u]; if(u!=v) { vec[u].push_back(v) ; vec[v].push_back(u) ; } }}//dp[u][1],dp[u][0] 分别表示以u节点为根节点的子树与其最远和第二远的节点的距离void dfs(const int u , int &ans){ vis[u] = 1 ; for(int i = 0;i < vec[u].size();i++) { int v = vec[u][i]; if(vis[v])continue ; dfs(v , ans); if(dp[v][1] + 1 > dp[u][1]) { dp[u][0] = max(dp[u][0] , dp[u][1]); dp[u][1] = dp[v][1] + 1 ; } else dp[u][0] = max(dp[u][0] , dp[v][1] + 1); } ans = max(ans , dp[u][0] + dp[u][1]) ;}//一棵树的直径可以通过两次bfs找到//一次从任意结点开始，找与其距离最大的点，，然后从该点开始，//再一次遍历到与其最远的节点的距离即为该树的直径/*queue<int> que ;int bfs( const int st , int &ans){ while(que.size())que.pop() ; que.push(st) ; que.push(0) ; vis[st] = 1 ; int en = st; ans = 0 ; while(que.size()) { int u = que.front() ;que.pop() ; int step = que.front();que.pop() ; if(step > ans) { ans = step; en = u ; } for(int i = 0;i < vec[u].size() ;i++) { int v = vec[u][i] ; if(vis[v])continue ; vis[v] = 1 ; que.push(v); que.push(step+1); } } return en ;}*/int main(){ //freopen("in.txt" , "r" , stdin) ; while(scanf("%d%d" , &n , &m) , n+m) { init() ; for(int i = 1;i <= m;i++) { int a , b ; scanf("%d%d" , &a , &b) ; addedge(a , b) ; addedge(b , a) ; } tarjan(1) ; build_tree() ; int ans = 0 ; memset(vis , 0 ,sizeof(vis)) ; dfs(1 , ans) ; //bfs(bfs(1 , ans) , ans); printf("%d\n" , num – 1 – ans) ; } return 0 ;}
我要扼住命运的咽喉。
