无向图双连通分量（DCC）

目录

1.边连通分量

 1.冗余路径

2.点连通分量

 1.电力

2.矿场搭建

---

1.边连通分量

边连通分量（e-DCC）： 就是删除无向图的一条边，假如该图不连通了，则这条边叫做桥，边连通分量就是极大的不含桥的连通分量

1.弄连个时间戳dfn表示第一次遍历到这个点的时间戳，low是他的子树中的最小的时间戳

2.假如是桥，则dfn[x]y这条边就是桥

3.用stack存边连通分量，因为假如low[x]==dfn[x],说明找到了这个点的祖宗节点，则入栈的就是他的子树，也就是边连通分量

 1.冗余路径

395. 冗余路径 - AcWing题库

题目大意就是：给定一个无向连通图，问最少加多少条边，使得该图变成一个边双连通分量

先做一遍边的双连通分量，然后缩点建图，变成一棵树，答案就叶节点（也即度数为1的点）的一半向上取整，则ans=[cnt+1]/2

#include
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]//假如是桥
                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//枚举一下所有的边
      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<
    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
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//枚举每个为根
          if(!dfn[root])//假如不在任何一个连通块中
          {
              cnt++;//则新开个连通块
             tarjan(root);//遍历一遍
          }
      printf("%d\n",cnt+ans-1);
   }
    return 0;
}

2.矿场搭建

396. 矿场搭建 - AcWing题库

题意：给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通 

 

#include
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//枚举该连通块的点
            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;
}