低价网站建设湘潭,做网站设计的电脑需要什么配置,青岛新网站设计公司,网站投稿源码题干#xff1a;
网络管理员管理大型网络。该网络由N台计算机和成对计算机之间的M链路组成。任何一对计算机都通过连续的链接直接或间接连接#xff0c;因此可以在任何两台计算机之间转换数据。管理员发现某些链接对网络至关重要#xff0c;因为任何一个链接的故障都可能导…题干
网络管理员管理大型网络。该网络由N台计算机和成对计算机之间的M链路组成。任何一对计算机都通过连续的链接直接或间接连接因此可以在任何两台计算机之间转换数据。管理员发现某些链接对网络至关重要因为任何一个链接的故障都可能导致某些计算机之间无法转换数据。他把这种联系称为桥梁。他计划逐一添加一些新链接以消除所有桥梁。 您将通过在添加每个新链接后报告网络中的网桥数来帮助管理员。
输入
输入包含多个测试用例。每个测试用例以包含两个整数N1≤N≤100,000和MN-1≤M≤200,000的行开始。 以下M行中的每一行包含两个整数A和B1≤A≠B≤N表示计算机A和B之间的链接。计算机编号从1到N.保证任何两台计算机都连接在一起最初的网络。 下一行包含一个整数Q1≤Q≤1,000这是管理员计划逐个添加到网络的新链接数。 以下Q行的第i行包含两个整数A和B1≤A≠B≤N这是连接计算机A和B的第i个新链接。 最后一个测试用例后跟一行包含两个零的行。
输出
对于每个测试用例打印一行包含测试用例编号以1开头和Q行其中第i行包含一个整数表示添加第一个i新链接后网络中的网桥数。在每个测试用例的输出后打印一个空行。
Sample Input
3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0
Sample Output
Case 1:
1
0Case 2:
2
0
题目大意 给了一个连通图。 问加入边的过程中桥的个数。
解题报告 在线维护桥的个数就可以了。注意缩点的使用。
AC代码1对dfn求lca暴力1157ms
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
struct Edge {int u,v;int ne;
} e[MAX1];
int dfn[MAX],low[MAX],clk;
int head[MAX],tot,fa[MAX];
int qiao[MAX];
int n,m,ans;
void init() {for(int i 1; in; i) {dfn[i]low[i]qiao[i]fa[i]0;//如果不初始化fahead[i] -1;}tot 0;clk 0;ans 0;
}
void add(int u,int v) {e[tot].u u;e[tot].v v;e[tot].ne head[u];head[u] tot;
}
void tarjan(int x,int rt) {//注意这里fa和rt是不一样的含义dfn[x] low[x] clk;fa[x] rt;for(int i head[x]; ~i; i e[i].ne) {int v e[i].v;if(v rt) continue;if(dfn[v] 0) {tarjan(v,x);low[x] min(low[x],low[v]);if(low[v] dfn[x]) {qiao[v] 1;ans;}} else low[x] min(low[x],dfn[v]);}
}
void lca(int u, int v) {while(dfn[v] dfn[u]) {if(qiao[v]) ans--;qiao[v] 0;v fa[v];}while(dfn[u] dfn[v]) {if(qiao[u]) ans--;qiao[u] 0;u fa[u];}while(u ! v) {if(qiao[u]) ans--;if(qiao[v]) ans--;qiao[u] qiao[v] 0;u fa[u];v fa[v];}
}
int main()
{int a,b,iCase0;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;init();for(int i 1; im; i) {scanf(%d%d,a,b);add(a,b); add(b,a);}tarjan(1,0);int q;scanf(%d,q);printf(Case %d:\n,iCase);while(q--) {scanf(%d%d,a,b);lca(a,b);printf(%d\n, ans);}printf(\n);}return 0 ;
}其实对上面这个代码的lca函数做了很多无用的工作因为u和v最后可能都会回到1顶点。
实测这样写也可以过969ms
void lca(int u, int v) {if(dfn[u] dfn[v]) swap(u,v); while(dfn[v] dfn[u]) {if(qiao[v]) ans--;qiao[v] 0;v fa[v];}while(u ! v) {if(qiao[u]) ans--;qiao[u] 0;u fa[u];}
}
AC代码2缩点lca2891ms
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
struct Edge {int u,v;int ne;
} e[MAX1];
vectorint vv[MAX];
int dep[MAX];
int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc;
int head[MAX],tot,fa[MAX];
int qiao[MAX],is[MAX];//qiao数组用来记录原图中的每一个点是否是桥的终点is数组用来记录构造的那棵树上的每一个新顶点编号是否还没被遍历过。 也就是用一个点去代表这个边双连通分量
int n,m,ans;
void init() {for(int i 1; in; i) {dfn[i]low[i]qiao[i]fa[i]is[i]col[i]0;head[i] -1;vv[i].clear();}tot 0;clk index bcc 0;ans 0;
}
void add(int u,int v) {e[tot].u u;e[tot].v v;e[tot].ne head[u];head[u] tot;
}
void tarjan(int x,int rt) {dfn[x] low[x] clk;stk[index] x;for(int i head[x]; ~i; i e[i].ne) {int v e[i].v;if(v rt) continue;if(dfn[v] 0) {tarjan(v,x);low[x] min(low[x],low[v]);if(low[v] dfn[x]) {qiao[v] 1;ans;}} else low[x] min(low[x],dfn[v]);}if(dfn[x] low[x]) {bcc;//理论上来说应该等于ans1 while(1) {int tmp stk[index];index--;col[tmp] bcc;if(tmp x) break;}}
}
void bfs() {queueint q;q.push(1);//initfor(int i 1; in; i) dep[i]0,is[i]0;is[1]0;dep[1]1;fa[1] -1;//人为规定一个 while(!q.empty()) {int cur q.front();q.pop();int up vv[cur].size();for(int i 0; iup; i) {int v vv[cur][i];if(dep[v]) continue;dep[v] dep[cur] 1;fa[v] cur;is[v]1; q.push(v); }}
}
void lca(int u,int v) {if(dep[u] dep[v]) swap(u,v);while(dep[u] dep[v]) {if(is[u]) ans--,is[u]0;u fa[u];} if(u v) return;while(u ! v) {if(is[u]) ans--,is[u]0;if(is[v]) ans--,is[v]0;u fa[u];v fa[v];}
}
int main()
{int a,b,iCase0;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;init();for(int i 1; im; i) {scanf(%d%d,a,b);add(a,b); add(b,a);}tarjan(1,0);for(int u 1; un; u) {for(int i head[u]; ~i; i e[i].ne) {int v e[i].v;if(qiao[v] 0) continue;vv[col[u]].pb(col[v]);vv[col[v]].pb(col[u]);}}bfs();int q;scanf(%d,q);printf(Case %d:\n,iCase);while(q--) {scanf(%d%d,a,b);lca(col[a],col[b]);//每次暴力a的bcc 到 b的bcc这条路径。 printf(%d\n, ans);}printf(\n);}return 0 ;
}AC代码3454ms
因为对于无向图的tarjan算法有一个性质就是你只要搜素进去那肯定就把这一个bcc全都搜完然后再进入另一个。
换种方向考虑因为是搜索所以对于查询的两个点u和v肯定有个他俩的共同起点祖先而由于搜索的特性所以dfn[u]一直减小通过让ufa[u]当dfn[u]dfn[v]的时候此时的u要么是v要么是u和v的最近公共祖先。
对于很多跑的飞快400ms左右的代码多半是用并查集来写的把qiao数组换成了并查集来看差不多这样然后改一下 tarjan函数的关键点部分 和 lca函数的部分但是对于lca部分也是暴力那么为什么会快这么多呢研究了半天发现就是因为他在进入lca函数之前加了一句if(col[a] ! col[b]) 代码如下
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
struct Edge {int u,v;int ne;
} e[MAX1];
vectorint vv[MAX];
int dep[MAX];
int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc;
int head[MAX],tot,fa[MAX];
int qiao[MAX],is[MAX];//qiao数组用来记录原图中的每一个点是否是桥的终点is数组用来记录构造的那棵树上的每一个新顶点编号是否还没被遍历过。
int n,m,ans;
void init() {for(int i 1; in; i) {dfn[i]low[i]qiao[i]fa[i]is[i]col[i]0;head[i] -1;vv[i].clear();}tot 0;clk index bcc 0;ans 0;
}
void add(int u,int v) {e[tot].u u;e[tot].v v;e[tot].ne head[u];head[u] tot;
}
void tarjan(int x,int rt) {dfn[x] low[x] clk;stk[index] x;fa[x] rt;for(int i head[x]; ~i; i e[i].ne) {int v e[i].v;if(v rt) continue;if(dfn[v] 0) {tarjan(v,x);low[x] min(low[x],low[v]);if(low[v] dfn[x]) {qiao[v] 1;ans;}} else low[x] min(low[x],dfn[v]);}if(dfn[x] low[x]) {bcc;//理论上来说应该等于ans1 while(1) {int tmp stk[index];index--;col[tmp] bcc;if(tmp x) break;}}
}
void lca(int u, int v) {if(dfn[u] dfn[v]) swap(u,v); while(dfn[v] dfn[u]) {if(qiao[v]) ans--;qiao[v] 0;v fa[v];}while(u ! v) {if(qiao[u]) ans--;qiao[u] 0;u fa[u];}
}
int main()
{int a,b,iCase0;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;init();for(int i 1; im; i) {scanf(%d%d,a,b);add(a,b); add(b,a);}tarjan(1,0);int q;scanf(%d,q);printf(Case %d:\n,iCase);while(q--) {scanf(%d%d,a,b);if(col[a] ! col[b]) lca(a,b);//每次暴力a的bcc 到 b的bcc这条路径。 printf(%d\n, ans);}printf(\n);}return 0 ;
}
思考
对于AC代码1中的那个改进我们拿到AC代码2的思路来行不行呢
答案是不行的因为你将图转化成了一棵树然后用bfs生成的dep数组去做lcalca做法也是先把u设置成dep大的然后让u一直向上找,一直到dep[u] dep[v]则第一个循环结束然后再只动v一直到uv则第二个循环结束那么得到的当dep[u] dep[v]了之后不能确保此时的u要么等于v要么是u和v的最近公共祖先想想普通的倍增做的lca的图呀很容易找到反例所以不能这样做不然会出现v1了但是u还在下面这样就死循环了所以会TLE。
TLE代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
struct Edge {int u,v;int ne;
} e[MAX1];
vectorint vv[MAX];
int dep[MAX];
int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc;
int head[MAX],tot,fa[MAX];
int qiao[MAX],is[MAX];//qiao数组用来记录原图中的每一个点是否是桥的终点is数组用来记录构造的那棵树上的每一个新顶点编号是否还没被遍历过。
int n,m,ans;
void init() {for(int i 1; in; i) {dfn[i]low[i]qiao[i]fa[i]is[i]col[i]0;head[i] -1;vv[i].clear();}tot 0;clk index bcc 0;ans 0;
}
void add(int u,int v) {e[tot].u u;e[tot].v v;e[tot].ne head[u];head[u] tot;
}
void tarjan(int x,int rt) {dfn[x] low[x] clk;stk[index] x;for(int i head[x]; ~i; i e[i].ne) {int v e[i].v;if(v rt) continue;if(dfn[v] 0) {tarjan(v,x);low[x] min(low[x],low[v]);if(low[v] dfn[x]) {qiao[v] 1;ans;}} else low[x] min(low[x],dfn[v]);}if(dfn[x] low[x]) {bcc;//理论上来说应该等于ans1 while(1) {int tmp stk[index];index--;col[tmp] bcc;if(tmp x) break;}}
}
void bfs() {queueint q;q.push(1);//initfor(int i 1; in; i) dep[i]0,is[i]0;is[1]0;dep[1]1;fa[1] -1;//人为规定一个 while(!q.empty()) {int cur q.front();q.pop();int up vv[cur].size();for(int i 0; iup; i) {int v vv[cur][i];if(dep[v]) continue;dep[v] dep[cur] 1;fa[v] cur;is[v]1; q.push(v); }}
}
void lca(int u,int v) {if(dep[u] dep[v]) swap(u,v);while(dep[u] dep[v]) {if(is[u]) ans--,is[u]0;u fa[u];} if(u v) return;while(u ! v) {if(is[v]) ans--,is[v]0;v fa[v];}
}
int main()
{int a,b,iCase0;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;init();for(int i 1; im; i) {scanf(%d%d,a,b);add(a,b); add(b,a);}tarjan(1,0);for(int u 1; un; u) {for(int i head[u]; ~i; i e[i].ne) {int v e[i].v;if(qiao[v] 0) continue;vv[col[u]].pb(col[v]);vv[col[v]].pb(col[u]);}}bfs();int q;scanf(%d,q);printf(Case %d:\n,iCase);while(q--) {scanf(%d%d,a,b);if(col[a] ! col[b]) lca(col[a],col[b]);//每次暴力a的bcc 到 b的bcc这条路径。 printf(%d\n, ans);}printf(\n);}return 0 ;
}
