首页 > 其他分享 >P8435 【模板】点双连通分量

P8435 【模板】点双连通分量

时间:2024-02-25 17:24:15浏览次数:25  
标签:cnt 点双 int back P8435 ans push now 模板

原题链接

题解

唯一能解释的图片,黄色代表会执行入栈操作的点

code

#include<bits/stdc++.h>
using namespace std;

int vis[500005]={0};
int low[500005]={0};
stack<int> q;
vector<int> ans[500005];
vector<int> G[500005];
int len=0;
int cnt=0;

void ss(int now,int fa)
{
    //cout<<now<<endl;
    vis[now]=++len;
    low[now]=len;
    q.push(now);
    int son=0;
    for(auto next:G[now])
    {
        if(next==fa)continue;

        son++;
        if(vis[next]) low[now]=min(low[now],vis[next]);
        else
        {
            ss(next,now);
            if(low[next]>=vis[now])
            {
                cnt++;
                int x;
                do
                {
                    x=q.top();
                    ans[cnt].push_back(x);
                    q.pop();
                }while(next!=x);
                ans[cnt].push_back(now);
            }
            else low[now]=low[next];
        }
    }
    if(now==fa&&son==0)
    {
        ans[++cnt].push_back(now);
        q.pop();
    }
}
int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(!vis[i]) ss(i,i);

    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i].size()<<" ";
        for(auto val:ans[i]) cout<<val<<" ";
        puts("");
    }
    return 0;
}

标签:cnt,点双,int,back,P8435,ans,push,now,模板
From: https://www.cnblogs.com/pure4knowledge/p/18032626

相关文章

  • P3388 【模板】割点(割顶)
    原题链接题解先说结论对单个图做深度搜索树,对于树的根节点,它要能是割点当且仅当她有至少两个不互通的儿子节点对于树的非叶子非根节点,它要能是割点当且仅当存在儿子节点能去的时间戳最小的节点不小于当前节点的深度搜索序对于叶子节点,不可能成为割点code#include<bits/std......
  • JavaScript语法-字符串模板
    [TOC]##JavaScript模板字符串###代码以下是index.js的部分代码:```onShareAppMessage({const{toName,mainText,fromName}=this.data;debugger;return{title:'叮,您收到一张贺卡~',path:'pages/index/index?toname=${toName}&mai......
  • C# 的布尔类型和字符串类型(模板字符串)
    //布尔类型bollboolb=false;b=1==1;//trueboolb1=1>23;//false//值类型:在代码中初始化类型的时候没有赋值但是系统会自动赋值的叫值类型//byteshortint(default0)longfloatdou......
  • U107394 拓扑排序模板
    原题链接在拓扑排序的基础上加上了一个条件:尽可能按字典序排序,这就使得题目难度加大。题解:拓扑排序+小根堆拓扑排序是采用队列一个一个出队列来删除对应结点的边,那么我们只需要保证每次出队列的结点都尽可能小,就能保证字典序。每次出队列的值都为队列中的最小值,刚好可以采用小......
  • poly模板
    多项式全家桶#include<bits/stdc++.h>#defineFu(i,a,b)for(registerinti=a;i<=b;i++)#defineFd(i,a,b)for(inti=a;i>=b;i--)#definemod998244353usingnamespacestd;intksm(inta,intk){ intans=1; while(k){ if(k&1)ans=1ll*ans*a%mod; ......
  • 我的模板
    StringsHashtemplate<intN>structStringHashing{chars[N];i64mod[2]={1610612741ll,805306457ll};i64pw[N][2];i64w[N][2];voidinit(intm){pw[0][0]=pw[0][1]=1;for(inti=1;i<=m;++i){pw[i][0]=......
  • 模拟退火模板
    模拟退火模板#include<bits/stdc++.h>#defineMAX_TIME0.9//时间限制(s)#defineFu(i,a,b)for(registerinti=(a);i<=(b);i++)usingnamespacestd;doubleRand(){return1.0*rand()/RAND_MAX;}intcalc(intz,ints[605],intx){//计算差值 if(ans<=)//更新按时......
  • 线段树模板
    向上回溯voidpushup(intrt){ t[rt].sum+=t[lc].sum+t[rc].sum; t[rt].mx=max(t[lc].mx,t[rc].mx);}建树voidbuild(intrt,intl,intr){ t[rt].l=l; t[rt].r=r; if(l==r){ t[rt].mx=t[rt].sum=a[l]; return; } intmid=(l+r)>>1......
  • DFS算法模板(2488:A Knight's Journey)
    DFS算法(C++版本)题目一:链接:http://bailian.openjudge.cn/practice/2488/解析思路:骑士找路就是基本的DFS,用递归不断找到合适的路,找不到就回头直到找到合适的路。该题难点:要是实现字典序,也就是同样的两种选择,要走到A1而不是B1。所以就有了{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1......
  • 回溯算法模板 & 78子集代码
     voidbacktracking(参数){   if(终止条件){       存放结果;       return;   }   for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){       处理节点;       backtracking(路径,选择列表);//递归       ......