【题意】:
有N个结点M条边的图,有Q次操作,每次操作在点x, y之间加一条边,加完E(x, y)后还有几个桥(割边),每次操作会累积,影响下一次操作。
【思路】:
先用Tarjan求出一开始总的桥的数量,然后求边双联通分量并记录每个结点v所属的连通分量号c[v],之后进行缩点,将每个双联通分量作为都缩成一个新点,如果新点之间可以连边就连边
(能不能连边取决于原图,我就不多bb辽,XD),形成新图。
对于每次询问x, y,判断c[x]!=c[y],然后从c[x]和c[y]分别向上寻找父结点,找到LCA,对c[x]寻找时经过的边数 对c[y]寻找时经过的边数==应该减去的桥数。
考虑到每次操作的累加性,已经在之前操作中经过的边已经不是桥,不能在后续操作中再进行统计,所以使用并查集,每当c[x],c[y]找到lca时,就将pre[c[x]] = pre[c[y]] = lca。
求LCA时涉及几乎涉及到每条边,就不使用倍增LCA(主要是我不会??),而是用定义的方法。
下面上代码,第一个代码是求了桥,然后再进行求强联通分量,再加边。 第二个是先求强联通分量(当然是有限制的,不然因为整个图就是联通的,肯定就一个SCC了),再加边。
个人倾向于第二种袄,而且速度快
#include <iostream> #include <cstring> #include <cstdio> #include <map> #include <map> using namespace std; const int maxn = 1e6 5; const int maxm = maxn<<1; struct edge{ int to, next; } ed[maxm<<1]; int n, m, q; int head[maxn], tot; int dfn[maxn], low[maxn], num, ans, c[maxn], dcc; int hc[maxn], vc[maxm<<1], nc[maxm<<1], tc; int pre[maxn], fa[maxn], dep[maxn], pass; bool brige[maxn], vis[maxn]; inline void init(){ memset( head, -1, sizeof(head) ); memset( dfn, 0, sizeof(dfn) ); memset( brige, 0, sizeof(brige) ); memset( c, 0, sizeof(c) ); memset( vis, 0, sizeof(vis) ); tot = 1; } inline void add( int u, int v ){ ed[ tot].to = v; ed[tot].next = head[u]; head[u] = tot; ed[ tot].to = u; ed[tot].next = head[v]; head[v] = tot; } inline int min( int a, int b ){ return a<b ? a:b; } inline void tarjan( int x, int in_edge ){ dfn[x] = low[x] = num; for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if(!dfn[y]){ tarjan(y, i); low[x] = min(low[x], low[y]); if( dfn[x]<low[y] ){ brige[i] = brige[i^1] = 1; ans ; } }else if( i!=(in_edge^1) ) low[x] = min(low[x], dfn[y]); } } inline void add_dcc( int u, int v ){ vc[ tc] = v; nc[tc] = hc[u]; hc[u] = tc; } inline void dfs_dcc( int x ){ c[x] = dcc; for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( brige[i] || c[y] ) continue; dfs_dcc(y); } } inline int find( int x ){ return pre[x]==x ? x:pre[x] = find(pre[x]); } inline void dfs_lca( int x ){ //结点分层 pre[x] = x; for( int i=hc[x]; i!=-1; i=nc[i] ){ int y = vc[i]; if( y!=fa[x] ){ fa[y] = x; dep[y] = dep[x] 1; dfs_lca(y); } } } inline void LCA( int x, int y ){ pass = 0; x = find(x); y = find(y); //直接将x,y向上寻找的路径中已经计算过得边略过 while( dep[y]!=dep[x] ){ if( dep[y]>dep[x] ){ int f = find(fa[y]); //当pre[y] == y时f是y的父亲,当pre[y]在y上方时,f就是相当于爷爷或者更高的祖辈 y = pre[y] = f; //不能写成pre[y] = y = f这样y先被赋值,pre[y]则改变的是赋值后的y即pre[f]被改变 pass ; }else{ int f = find(fa[x]); x = pre[x] = f; pass ; } } while( find(x)!=find(y) ){ pre[x] = find(fa[x]); pre[y] = find(fa[y]); x = pre[x]; y = pre[y]; pass = 2; } } int main(){ // freopen("in.txt", "r", stdin); int kase = 1; while( ~scanf("%d%d", &n, &m), n||m ){ init(); for( int i=0; i<m; i ){ int u, v; scanf("%d%d", &u, &v); add(u, v); } ans = dcc = num = 0; tarjan(1, 0); for( int i=1; i<=n; i ) if( !c[i] ) dcc, dfs_dcc(i); memset( hc, -1, sizeof(hc) ); tc = 1; //不要使用map作为标记,遍历边进行新图的加边操作,map会TLE for( int u=1; u<=n; u ){ for( int i=head[u]; i!=-1; i=ed[i].next ){ int v = ed[i].to; if( c[u]==c[v] ) continue; add_dcc(c[u], c[v]); } } ans = tc>>1; dep[1] = 1; fa[1] = 0; dfs_lca(1); scanf("%d", &q); printf("Case %d:n", kase ); while( q-- ){ int x, y; scanf("%d%d", &x, &y); if( c[x]!=c[y] ){ LCA(c[x], c[y]); ans -= pass; } printf("%dn", ans); } puts(""); } return 0; }先求桥,再求边双联通,再连边进行LCA
#include <iostream> #include <cstring> #include <cstdio> #include <map> #include <map> using namespace std; const int maxn = 1e6 5; const int maxm = maxn<<1; struct edge{ int to, next; } ed[maxm<<1]; int n, m, q; int head[maxn], tot, st[maxn]; int dfn[maxn], low[maxn], num, ans, c[maxn], dcc; int hc[maxn], vc[maxm<<1], nc[maxm<<1], tc; int pre[maxn], fa[maxn], dep[maxn], pass; bool ins[maxn], vis[maxn]; inline void init(){ memset( head, -1, sizeof(head) ); memset( dfn, 0, sizeof(dfn) ); memset( c, 0, sizeof(c) ); memset( vis, 0, sizeof(vis) ); tot = 1; } inline void add( int u, int v ){ ed[ tot].to = v; ed[tot].next = head[u]; head[u] = tot; ed[ tot].to = u; ed[tot].next = head[v]; head[v] = tot; } inline int min( int a, int b ){ return a<b ? a:b; } inline void tarjan( int x, int in_edge ){ dfn[x] = low[x] = num; ins[x] = 1; st[ st[0]] = x; for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( i==(in_edge^1) ) continue; if(!dfn[y]){ tarjan(y, i); low[x] = min(low[x], low[y]); }else if( ins[y] ) low[x] = min(low[x], dfn[y]); } if( dfn[x]==low[x] ){ dcc ; int p; do{ p = st[st[0]--]; c[p] = dcc; ins[p] = 0; }while( p!=x ); } } inline void add_dcc( int u, int v ){ vc[ tc] = v; nc[tc] = hc[u]; hc[u] = tc; } inline int find( int x ){ return pre[x]==x ? x:pre[x] = find(pre[x]); } inline void dfs_lca( int x ){ pre[x] = x; for( int i=hc[x]; i!=-1; i=nc[i] ){ int y = vc[i]; if( y!=fa[x] ){ fa[y] = x; dep[y] = dep[x] 1; dfs_lca(y); } } } inline void LCA( int x, int y ){ pass = 0; x = find(x); y = find(y); while( dep[y]!=dep[x] ){ if( dep[y]>dep[x] ){ int f = find(fa[y]); //当pre[y] == y时f是y的父亲,当pre[y]在y上方时,f就是相当于爷爷或者更高的祖辈 y = pre[y] = f; //不能写成pre[y] = y = f这样y先被赋值,pre[y]则改变的是赋值后的y即pre[f]被改变 pass ; }else{ int f = find(fa[x]); x = pre[x] = f; pass ; } } while( find(x)!=find(y) ){ pre[x] = find(fa[x]); pre[y] = find(fa[y]); x = pre[x]; y = pre[y]; pass = 2; } } int main(){ // freopen("in.txt", "r", stdin); int kase = 1; while( ~scanf("%d%d", &n, &m), n||m ){ init(); for( int i=0; i<m; i ){ int u, v; scanf("%d%d", &u, &v); add(u, v); } ans = dcc = num = 0; for( int i=1; i<=n; i ) if(!dfn[i]) tarjan(1, 0); memset( hc, -1, sizeof(hc) ); tc = 1; for( int u=1; u<=n; u ){ for( int i=head[u]; ~i; i=ed[i].next ){ int v = ed[i].to; if( c[u]==c[v] ) continue; add_dcc(c[u], c[v]); } } ans = tc>>1; dep[1] = 1; fa[1] = 0; dfs_lca(1); scanf("%d", &q); printf("Case %d:n", kase ); while( q-- ){ int x, y; scanf("%d%d", &x, &y); if( c[x]!=c[y] ){ LCA(c[x], c[y]); ans -= pass; } printf("%dn", ans); } puts(""); } return 0; }求强联通分量,再加边,进行LCA