1.边连通分量
边连通分量（e-DCC）： 就是删除无向图的一条边，假如该图不连通了，则这条边叫做桥，边连通分量就是极大的不含桥的连通分量
1.弄连个时间戳dfn表示第一次遍历到这个点的时间戳，low是他的子树中的最小的时间戳
2.假如是桥，则dfn[x]<low[y]，则说明x->y这条边就是桥
3.用stack存边连通分量，因为假如low[x]==dfn[x],说明找到了这个点的祖宗节点，则入栈的就是他的子树，也就是边连通分量
1.冗余路径
题目大意就是：给定一个无向连通图，问最少加多少条边，使得该图变成一个边双连通分量
先做一遍边的双连通分量，然后缩点建图，变成一棵树，答案就叶节点（也即度数为1的点）的一半向上取整，则ans=[cnt+1]/2
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5010,M=20010; int n,m; int h[N],e[M],ne[M],idx; int dfn[N],low[N],timestamp; int stk[N],top; int id[N],dcc_cnt; bool is_bridge[M]; int d[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u, int from)//u是当前节点，from是从那个节点更新过来的 { dfn[u]=low[u]=++timestamp;//第一次遍历让她们都等于时间戳 stk[++top]=u;//把这个点入栈 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(!dfn[j])//假如没有遍历过 { tarjan(j,i);//遍历一遍 low[u]=min(low[u],low[j]); if(dfn[u]<low[j])//假如是桥 is_bridge[i]=is_bridge[i^1]=true;//正向边和反向边都是标记为桥，反向边就是i^1 } else if(i!=(from^1)) low[u]=min(low[u],dfn[j]);//假如正向边不等于转移过来的边，也即不是父节点，则更新 } if(dfn[u]==low[u])//假如相等了说明找到了一个连通块 { ++dcc_cnt;//连通块++ int y; do { y=stk[top--];//栈里的元素就是他的连通块元素 id[y]=dcc_cnt;//标记这个点是属于这个连通块的 }while(y!=u); } } int main() { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int a,b; cin>>a>>b; add(a,b),add(b,a); } tarjan(1,-1);//搜索一下所有的边 for(int i=0;i<idx;i++)//枚举一下所有的边 if(is_bridge[i])//假如这条边是桥 d[id[e[i]]]++;//则则这条边的上一个边连通分量度数++ int cnt=0; for(int i=1;i<=dcc_cnt;i++)//缩点后的图 if(d[i]==1) cnt++;//算一遍度数为1的边 cout<<(cnt+1)/2<<endl; return 0; }
2.点连通分量
点连通分量（v-DCC）：就是删除无向图的一个点，假如该图不连通了，则这个点叫做割点，点连通分量就是极大的不含割点的连通分量
1.弄连个时间戳dfn表示第一次遍历到这个点的时间戳，low是他的子树中的最小的时间戳
2.求割点：当low[y]>=dfn[x],
（1）假如x不是根节点，那么x是割点
（2）假如是根节点，至少有两个字节点yi使得low[yi]>=dfn[x],则x是割点
3.用stack存边连通分量，因为假如low[x]==dfn[x],说明找到了这个点的祖宗节点，则入栈的就是他的子树，也就是边连通分量
1.电力
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
1.统计连通块的个数cnt
2.枚举从那个连通块中删，在枚举连通块中删除那个点，假如删除这个点后该连通块变成了s个，则答案就是max(s+cnt-1)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=10010,M=30010; int n,m,ans,root; int h[N],e[M],ne[M],idx; int dfn[N],low[N],timestamp; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u) { dfn[u]=low[u]=++timestamp;//第一次遍历让她们都等于时间戳 int cnt=0;//记录删除割点后的连通块个数 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(!dfn[j])//假如没有遍历过 { tarjan(j);//遍历一遍 low[u]=min(low[u],low[j]); if(low[j]>=dfn[u]) cnt++;//假如是割点，则连通块++ } else low[u]=min(low[u],dfn[j]);//更新一遍最小值 } if(u!=root&&cnt) cnt++;//假如不是根，且连通块个数不为0，说明这个也是一个割点，则连通块个数+1 ans=max(ans,cnt);//更新一遍最大值 } int main() { while(scanf("%d%d",&n,&m),n||m) { memset(dfn,0,sizeof dfn);//清空，因为dfn兼具判重的作用 memset(h,-1,sizeof h);//清空 idx=timestamp=0;//清空状态 while(m--) { int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } ans=0; int cnt=0; for(root=0;root<n;root++)//枚举每个为根 if(!dfn[root])//假如不在任何一个连通块中 { cnt++;//则新开个连通块 tarjan(root);//遍历一遍 } printf("%d\n",cnt+ans-1); } return 0; }
2.矿场搭建
题意：给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int N=1010,M=510; int n,m,root; int h[N],e[M],ne[M],idx; int dfn[N],low[N],timestamp; int stk[N],top; int id[N],dcc_cnt; vector<int>dcc[N]; bool cut[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u) { dfn[u]=low[u]=++timestamp;//第一次遍历让她们都等于时间戳 stk[++top]=u; if(u==root&&h[u]==-1)//假如是孤立点 { dcc_cnt++; dcc[dcc_cnt].push_back(u); return; } int cnt=0;//记录子树的个数 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(!dfn[j])//假如没有遍历过 { tarjan(j);//遍历一遍 low[u]=min(low[u],low[j]); if(low[j]>=dfn[u]) { cnt++;//子树加1 if(u!=root||cnt>1) cut[u]=true;//假如不为根或者子树为>1则为割点 ++dcc_cnt; int y;//求割点中的点，也即点连通块的点，并放进队列中去 do { y=stk[top--]; dcc[dcc_cnt].push_back(y); }while(y!=j); dcc[dcc_cnt].push_back(u); } } else low[u]=min(low[u],dfn[j]);//更新一遍最小值 } } int main() { int T=1; while(cin>>m,m) { for(int i=1;i<=dcc_cnt;i++) dcc[i].clear();//清空 idx=n=timestamp=top=dcc_cnt=0;//初始化 memset(cut,0,sizeof cut);//清空割点 memset(dfn,0,sizeof dfn);//清空，因为dfn兼具判重的作用 memset(h,-1,sizeof h);//清空 while(m--) { int a,b; scanf("%d%d",&a,&b); n=max(n,max(a,b)); add(a,b),add(b,a); } for(root=1;root<=n;root++)//枚举每个为根 if(!dfn[root])//假如不在任何一个连通块中 tarjan(root);//遍历一遍 int res=0; ull num=1; for(int i=1;i<=dcc_cnt;i++)//枚举每一个连通块 { int cnt=0; int len=dcc[i].size(); for(int j=0;j<len;j++)//枚举该连通块的点 if(cut[dcc[i][j]])//假如是割点，则割点++ cnt++; if(cnt==0&&len>1) res+=2,num*=len*(len-1)/2;//假如不是割点且点的数量大于1 else if(cnt==0) res++;//假如不是割点点的数量为1,则为孤立点 else if(cnt==1) res++,num*=len-1;//假如有一个割点 } printf("Case %d: %d %llu\n",T++,res,num); } return 0; }
