HDU - 2460 Network(桥+LCA) - 公司荣誉 - 新余市思创暖通工贸有限公司
现在的位置: 主页 > 公司荣誉 > 文章正文
HDU - 2460 Network(桥+LCA)
作者:新余市思创暖通工贸有限公司 来源:www.jxsichuang.com 发布时间:2017-09-10 09:45:44
HDU - 2460 Network(桥+LCA)

题目大意:给出一张图,现在要往这张图上加边,问加完边后,这张图还有多少条桥

解题思路:求出连通分量,压缩成点,用桥连接,形成了棵树
每次添加边时,就找一下是否在同一个强连通分量内,如果在同一个强连通分量内,那么桥的数量不变
反之,求出两个点的LCA,并且把LCA到这两个点的桥全部去掉(因为加边后,形成了环,构成了一个新的强连通分量了)

#include #include using namespace std; #pragma comment(linker,/STACk:10240000,10240000) #define N 100010 #define M 400010 #define min(a, b) ((a) < (b) ? (a) : (b)) struct Edge{ int to, next; }E[M]; int n, m, tot, dfs_clock, bnum; int head[N], f[N], low[N], pre[N]; bool isbridge[N], mark[N]; void AddEdge(int u, int v) { E[tot].to = v; E[tot].next = head[u]; head[u] = tot++; u = u ^ v; v = u ^ v; u = u ^ v; E[tot].to = v; E[tot].next = head[u]; head[u] = tot++; } void init() { memset(head, -1, sizeof(head)); tot = 0; int u, v; for (int i = 0; i < m; i++) { scanf(%d%d, &u, &v); AddEdge(u, v); } } void dfs(int u, int fa) { low[u] = pre[u] = ++dfs_clock; bool flag = false; for (int i = head[u]; i != -1; i = E[i].next) { int v = E[i].to; if (v == fa && !flag) { flag = true; continue; } if (!pre[v]) { f[v] = u; dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] > pre[u]) { isbridge[v] = 1; bnum++; } } else if (pre[v] < pre[u]) { low[u] = min(low[u], pre[v]); } } } void LCA(int u, int v) { while (pre[u] > pre[v]) { if (isbridge[u]) { bnum--; isbridge[u] = 0; } u = f[u]; } while (pre[u] < pre[v]) { if (isbridge[v]) { bnum--; isbridge[v] = 0; } v = f[v]; } while (u != v) { while (pre[u] > pre[v]) { if (isbridge[u]) { bnum--; isbridge[u] = 0; } u = f[u]; } } } int cas = 1; void solve() { memset(pre, 0, sizeof(pre)); memset(isbridge, 0, sizeof(isbridge)); dfs_clock = bnum = 0; for (int i = 1; i <= n; i++) f[i] = i; dfs(1, -1); int q, u, v; scanf(%d, &q); printf(Case %d: , cas++); while (q--) { scanf(%d%d, &u, &v); LCA(u, v); printf(%d , bnum); } printf( ); } int main() { while (scanf(%d%d, &n, &m) != EOF && n + m) { init(); solve(); } return 0; }

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站制作公司 http://www.45qun.com


  • 上一篇:Python Base One - WCCW
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 新余市思创暖通工贸有限公司 ALL RIGHTS RESERVED.
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100