首页 > 其他分享 >洛谷-P3388 【模板】割点(割顶)

洛谷-P3388 【模板】割点(割顶)

时间:2022-08-25 23:00:59浏览次数:107  
标签:割顶 洛谷 int 割点 dfn low nex now

【模板】割点(割顶)

tarjan

学了一下割点,发现就是找 \(low[nex] \ge dfn[now]\) 的点,同时根的话要求有两个分支才能作为割点

搜索的时候如果 \(nex\) 没有被访问过,则直接继续搜,如果访问过,则尝试通过 \(dfn[nex]\) 来松弛自己的 \(low[now]\),因为只考虑当前点能跑到的最上面的点,这与 \(tarjan\) 缩点有所不同

显然割边割点这些概念都是在无向图中完成的

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e4 + 10;
vector<int>gra[maxn];
int dfn[maxn], low[maxn], tp = 0;
int cut[maxn], sum = 0;

void tarjan(int now, int isrt)
{
    dfn[now] = low[now] = ++tp;
    int ans = 0;
    for(int nex : gra[now])
    {
        if(dfn[nex] == 0)
        {
            tarjan(nex, 0);
            if(low[nex] >= dfn[now])
                ans++;
            low[now] = min(low[now], low[nex]);
        }
        else
            low[now] = min(low[now], dfn[nex]);
    }
    if(ans > isrt)
    {
        cut[now] = 1;
        sum++;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        gra[a].push_back(b);
        gra[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
        if(dfn[i] == 0) tarjan(i, 1);
    cout << sum << "\n";
    int cur = 0;
    for(int i=1; i<=n; i++)
    {
        if(cut[i])
        {
            if(cur++) cout << " ";
            cout << i;
        }
    }
    cout << "\n";
    return 0;
}

标签:割顶,洛谷,int,割点,dfn,low,nex,now
From: https://www.cnblogs.com/dgsvygd/p/16626068.html

相关文章

  • 洛谷P1001 A+B problem最全算法
    为防止大家说我误导新人,先放一个最不正常的代码。#include<iostream>usingnamespacestd;intmain(){inta,b;cin>>a>>b;cout<<a+b;ret......
  • 洛谷P4619 [SDOI2018]旧试题
    再做一遍,算是复健一下数论。题目链接Description\(T\)组数据,给出\(A,B,C\),求\[\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\]\(d\)表示正因子个数。答案对\(P=1......
  • 洛谷 P1162 填涂颜色
    题目链接:https://www.luogu.com.cn/problem/P1162试题分析:本题运用广搜,我们大体思路是这样的:首先,我们将起始位置放到队尾,然后,在队列不为空的情况下,我们要一直取队首并拓......
  • 洛谷 P1443 马的遍历
    题目链接:https://www.luogu.com.cn/problem/P1443试题分析:题目是一个比较经典的广搜题,首先我们要读入长,宽,和马起点的坐标,然后将其压入队尾;在队列不为空时,一直取队首并将其......
  • [洛谷] 日 祭
    TOT:[140]2022JULY[58]7.13注册洛谷,做出第一道入门题(用py3)[1]7.14[2]7.19开始学C++7.24学完基本语法,用C++做出第一道题(庆祝)[2]7.26[15]7.27首道黄标!(......
  • 洛谷-P2272 最大半连通子图
    最大半连通子图tarjan缩点后计算弱连通图,相当于\(DAG\)图中点最多的路径,计算最大弱连通子图的时候就检查每个子节点的最长路径数量注意该题的答案计算与边有关,要去重......
  • 洛谷 P1706 全排列问题
    题目链接:https://www.luogu.com.cn/problem/P1706试题分析:题目要求按照字典序输出自然数 1 到 n 所有不重复的排列,且每一序列中的数字也不重复,我们可以运用搜索,将搜索......
  • 洛谷 CF442C 紫 题解
    前言说实话这道题确实不太适合作为紫题,但是它的思路很妙,在此我详细解释一下每一步操作背后的原因。大致流程从前往后读入数组\(a\),对于一个下标\(pos\),若其满足\(a[......
  • 洛谷P4726 【模板】多项式指数函数(多项式 exp)
    题目https://www.luogu.com.cn/problem/P4726思路(略)是个板题,但是包含了很多多项式的基础板子,适合用来练手。据说递归版的好写(好抄),但是我猜测和fft类似,迭代版的应该常......
  • 【题解】 洛谷P3694 邦邦的大合唱站队
    发现尽管\(n\)比较大,但\(m\)非常小,于是考虑状压。记\(dp_{i}\)表示满足条件的乐队集合为\(i\)时的最小出队人数,\(dp_i=\min\{dp_{i\\xor\\1<<k}\}+w_{i\\xo......