差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:i_dont_know_png:potassium:connected_component [2020/05/15 03:37]
potassium 创建
+++ 2020-2021:teams:i_dont_know_png:potassium:connected_component [2020/05/22 19:52] (当前版本)
potassium codedoc -> code
@@ 行 8: / 行 8: @@
 SCC 主要用于缩点，每一个点仅属于一个 SCC。缩点后是一个 DAG ，在建新图过程中需要注意两点不应属于同一 SCC 。
-在[[https://paste.ubuntu.com/p/ytJvgzFMx8/|实现]]中，在遍历到 $p\rightarrow q$ 返祖边时，对于 ''%%low[p]%%'' 的更新， ''%%min(low[p],low[q])%%'' 和 ''%%min(low[p],dfn[q])%%'' 等价，均可正确计算出结果。这与点双连通分量是不同的。
+在实现中，在遍历到 $p\rightarrow q$ 返祖边时，对于 ''%%low[p]%%'' 的更新， ''%%min(low[p],low[q])%%'' 和 ''%%min(low[p],dfn[q])%%'' 等价，均可正确计算出结果。这与点双连通分量是不同的。
 模板题：[[https://www.luogu.com.cn/problem/P3387|缩点]]
+<hidden 参考实现>
+<code:c++>
+int sta[N],top;
+int col[N],num;
+int dfn[N],low[N],tot;
+int vis[N];
+void tarjan(int p){
+	dfn[p]=low[p]=++tot;
+	int i,q;
+	sta[++top]=p;vis[p]=1;
+	for(i=hd[p];i;i=e[i].n){
+		q=e[i].e;
+		if(!dfn[q])tarjan(q),low[p]=min(low[p],low[q]);
+		else if(vis[q])low[p]=min(low[p],low[q]);
+	}
+	if(dfn[p]==low[p]){
+		num++;
+		while(sta[top+1]!=p){
+			q=sta[top];
+			col[q]=num;
+			vis[q]=0;
+			top--;
+		}
+	}
+}
+</code>
+</hidden>
+\\
 ===== 点双连通分量 =====
@@ 行 18: / 行 50: @@
 v-DCC 主要用于判割点，每一个非割点仅属于一个 v-DCC ，割点可以同时属于多个 v-DCC 。
-在[[https://paste.ubuntu.com/p/C4kcX8KKR9/|实现]]中，如果某个点 p 是割点，它应当满足以下条件之一：
+在实现中，如果某个点 p 是割点，它应当满足以下条件之一：
   - p 是根节点，且以它为根的 dfs 树有大于一个分支；
@@ 行 26: / 行 58: @@
 模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=3394|点双]] [[https://www.luogu.com.cn/problem/P3388|割点]]
+<hidden 参考实现>
+<code:c++>
+int low[N],dfn[N],tot;
+int sta[N],top;
+int cut[N];
+vector<int>dcc[N];int dcc_cnt;
+void tarjan(int p,int f){
+	int q,i,child=0;
+	sta[++top]=p;
+	dfn[p]=low[p]=++tot;
+	for(i=hd[p];i;i=e[i].n){
+		q=e[i].e;
+		if(q==f)continue; // avoid return to fa
+		if(!dfn[q]){
+			tarjan(q,p);
+			low[p]=min(low[p],low[q]);
+			if(low[q]>dfn[p]);// i is cut-edge
+			if(low[q]>=dfn[p]){
+				// p is cut of branch q
+				if(f!=-1)cut[p]=1;
+				dcc[++dcc_cnt].pb(p);
+				int r;
+				do{
+					r=sta[top--];
+					dcc[dcc_cnt].pb(r);
+				}while(r!=q);
+			}
+			child++;
+		}
+		low[p]=min(low[p],dfn[q]);
+	}
+	if(f==-1){ // edge case: p is root
+		if(child>1)cut[p]=1; // 2 branch in dfs tree
+		if(hd[p]==0)dcc[++dcc_cnt].pb(p); // single point
+	}
+}
+</code>
+</hidden>
+\\
 ===== 边双连通分量 =====
@@ 行 33: / 行 108: @@
 无向图中的 e-DCC 和有向图中的 SCC 很相似，有的时候可以进行缩点。
-在[[https://paste.ubuntu.com/p/FycWTp4brs/|实现]]中， e-DCC 和 SCC 的实现方式也类似，只是加了一个不能走父边的限制。
+在实现中， e-DCC 和 SCC 的实现方式也类似，只是加了一个不能走父边的限制。
 模板题：[[https://www.luogu.com.cn/problem/P2860|边双]]
+<hidden 参考实现>
+<code:c++>
+struct Edge{
+	int e,n;
+}e[N<<1];
+int hd[N],cnt=1,n,m;
+void add(int a,int b){
+	e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
+}
+int sta[N],top;
+int col[N],num;
+int dfn[N],low[N],tot;
+int vis[N];
+int ban[M<<1];
+void tarjan(int p){
+	dfn[p]=low[p]=++tot;
+	int i,q;
+	sta[++top]=p;vis[p]=1;
+	for(i=hd[p];i;i=e[i].n){
+		q=e[i].e;
+		if(ban[i])continue;
+		if(!dfn[q]){
+			ban[i]=ban[i^1]=1;
+			tarjan(q),low[p]=min(low[p],low[q]);
+		}
+		else if(vis[q])low[p]=min(low[p],low[q]);
+	}
+	if(dfn[p]==low[p]){
+		num++;
+		while(sta[top+1]!=p){
+			q=sta[top];
+			col[q]=num;
+			vis[q]=0;
+			top--;
+		}
+	}
+}
+</code>
+</hidden>
+\\
 ===== 杂项 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具