首页 > 其他分享 >Tarjan缩点

Tarjan缩点

时间:2023-08-06 15:56:33浏览次数:38  
标签:缩点 Tarjan 点双 连通 int 割点 low 分量

P3225 [HNOI2012] 矿场搭建

一共只会删除一个点,将每个点双连通分量分三种情况讨论

第一种:点双连通分量没有割点,那么为了保证一定可以逃出去,至少需要两个点

第二种:点双连通分量有且只有一个割点,此处割点是绿色的点,那么对于这种点双连通分量

就需要在每个只有一个割点的双连通分量中设置一个逃生点

第三种:点双连通分量有割点并且大于一个,此处对于双连通分量 { 1,2,3 } 中有割点2 1,那么对于这种点双连通分量不需要做任何处理

因为只会塌方一个点,并且由第二种情况,每个只有一个割点的双连通分量都会设置一个逃生点,那么第三种双连通分量某个割点塌方的话

他依旧可以从另外的割点逃出去,一直逃到逃到只有一个割点的双连通分量

 

 

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;


const int N=505;

std::vector<int>edge[N],cc[N];

int dfn[N],low[N],cut[N],idx,m,cnt;
stack<int>stk;

void dfs(int x,int fa,int root){
    dfn[x]=low[x]=++idx;
    stk.push(x);
    int son=0;
    //判断孤立点
    if(x==root&&(int)edge[x].size()==0){
        cut[x]=1;
        ++cnt;
        cc[cnt].push_back(x);
        return;
    }
    for(auto y:edge[x]){
        if(!dfn[y]){
            dfs(y,x,root);
            son++;
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                cut[x]=1;
                ++cnt;
                cc[cnt].push_back(x);
                while(1){
                    int top=stk.top();
                    cc[cnt].push_back(top);
                    stk.pop();
                    if(top==y)break;
                }
            }
        }else if(y!=fa){
            low[x]=min(low[x],dfn[y]);
        }
    }  
    if(x==1&&son<=1)cut[x]=0;
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int cs=0;
    while(1){
        ++cs;
        int m;cin>>m;
        if(!m)break;
        int n=0;
        for(int i=1;i<=m;i++){
            int x,y;cin>>x>>y;
            edge[x].push_back(y);
            edge[y].push_back(x);
            n=max({n,x,y});
        }
        for(int i=1;i<=n;i++){
            low[i]=dfn[i]=cut[i]=0;
        }
        while(!stk.empty())stk.pop();
        idx=cnt=0;
        for(int i=1;i<=n;i++){
            if(!dfn[i])dfs(i,i,i);
        }
        cout<<"Case "<<cs<<": ";
        int ans1=0,ans2=1;
        for(int i=1;i<=cnt;i++){
            int ncut=0;
            for(auto j:cc[i])ncut+=cut[j];
            if(ncut==0){
                ans1+=2;
                ans2*=(int)cc[i].size()*((int)cc[i].size()-1)/2;
            }else if(ncut==1){
                ans1+=1;
                ans2*=(int)cc[i].size()-1;
            }
        }
        cout<<ans1<<' '<<ans2<<endl;
        for(int i=1;i<=n;i++)edge[i].clear(),cc[i].clear();
    }
    return 0;
}
View Code

 

标签:缩点,Tarjan,点双,连通,int,割点,low,分量
From: https://www.cnblogs.com/zhujio/p/17609495.html

相关文章

  • Tarjan 系列学习笔记
    最近在复习提高算法,所以学习复习笔记写的就比较多。Tarjan系列的算法主要针对于图论而言。Part\(1\)缩点缩点算是Tarjan算法最广泛的应用了。先讲拓扑序。在一个有向图中,若此图无环,我们称这个图是有向无环图,也叫DAG,我们可以用拓扑排序解决许多图上问题,简单思路是先把入......
  • tarjan(dcc-e)
    [冗余路径](395.冗余路径-AcWing题库)考虑无向图的边双连通分量。这个算法也叫Tarjan算法,且与有向图的强连通分量差不多。边双是指图中任意两点间都存在两条不相交的路径(或删去任意一条边后图仍然连通)。桥:切去这条边后,图不连通。由于这是无向图,所以定义中不包含横叉边。......
  • 图论强联通分量(tarjan)算法
    图论强联通分量(tarjan)算法#include<bits/stdc++.h>usingnamespacestd;intn,m,cnt,cntb,ans;vector<int>edge[101];vector<int>belong[101];boolinstack[101];intdfn[101];intlow[101];stack<int>s;voidTarjan(intu){ ++cnt; dfn[u]=......
  • wsr_tarjan
    Tarjan首先是概念:极大强连通分量:不能再加入一点保持整个图强连通的图强连通分量:从任意一点能到达另一任意一点的图Tarjan原理树边 :在树上(图中黑色边)横插边 :从一棵子树到另一棵子树的边(图中绿色边)3、 返祖边 :连到自己的祖先的边观察图,我们可以注意到:横插......
  • LCA 离线tarjan算法
    tarjan算法是离线算法,它必须先将所有的要查询的点对存起来,然后在搜的时候输出结果。tarjan算法很经典,因为算法的思想很巧妙,利用了并查集思想,在dfs下,将查询一步一步的搜出来。伪代码如下:可以看到,对于我们已经保存好的查询,假设为(u,v),u为此时已经搜完的子树的根节点,v的位置就只有两种......
  • tarjan 学习笔记
    tarjan学习笔记求解强联通分量我们从一个点开始建立dfs树,有如下四种边:树边若\(u\)到\(v\)有边,且满足\(v\)没有被访问过,则这条边为树边返祖边若\(u\)到\(v\)有边,且满足\(v\)已被访问过,则这条边为返祖边横叉边若\(u\)到\(v\)有边,且满足\(u\)和......
  • 【学习笔记】Tarjan
    前言:凡事都得靠自己--bobo催隔壁K8Hen天了让他写Tarjan的学习笔记,但貌似还没有动静,所以决定自己写一个。正文本文配套题单:14.图论-tarjan(强连通分量、割点、割边)前置知识熟练使用链式前向星强连通、强连通图、强连通分量的定义(详见oi-wiki,这里不再赘述)如图......
  • BZOJ 2730: [HNOI2012]矿场搭建 tarjan割点
    2730:[HNOI2012]矿场搭建TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 2010  Solved: 935[Submit][Status][Discuss]Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口......
  • BZOJ 2140: 稳定婚姻 tarjan
    2140:稳定婚姻TimeLimit: 2Sec  MemoryLimit: 259MBSubmit: 764  Solved: 355[Submit][Status][Discuss]Description我国的离婚率连续7年上升,今年的头两季,平均每天有近5000对夫妇离婚,大城市的离婚率上升最快,有研究婚姻问题的专家认为,是与简化离婚手续有关。25......
  • BOZJ 1123: [POI2008]BLO tarjan求割点
    1123:[POI2008]BLOTimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 1140  Solved: 505[Submit][Status][Discuss]DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.所有towns连通。Input输入n<=100000m<=5......