图的连通性

强连通分量 tarjan c++14

struct scc{
    const int nn;
    int cnt,idx;
    vector col,dfn,low,stk;
    vector onstk;
    vector > g,comp;
    scc(int n1):nn(n1),cnt(0),idx(0),col(n1),dfn(n1,0),low(n1),stk(n1),onstk(n1,0),g(n1){}
    void add_edge(int u,int v)
    {
        g[u].push_back(v);
    }
    void dfs(int u,int fr)
    {
        dfn[u]=low[u]=++cnt;
        int child=0,time=0;
        for(auto [v,i]:g[u])
        {
            if(v==fr&&time==0)
            {
                time++;
                continue;
            }
            if(!dfn[v])
            {
                child++;
                dfs(v,u);
                if(u==fr&&child>=2)
                    point[u]=1;
                if(u!=fr&&low[v]>=dfn[u]&&child>=1)
                    point[u]=1;
                low[u]=min(low[u],low[v]);
            }
            if(fr!=v)
                low[u]=min(low[u],dfn[v]);
            if(low[v]>dfn[u])
                bridges.push_back(i);
        }
    }
    void solve()
    {
        for(int i=0;i 
割点和桥tarjan
 
struct Bridge{
    const int nn;
    int cnt;
    vector dfn,low,bridges,point;
    vector > > g;
    Bridge(int n1):nn(n1),cnt(0),dfn(n1,0),low(n1),point(n1,0),g(n1){}
    void add_edge(int u,int v,int i)
    {
        g[u].emplace_back(v,i);
        g[v].emplace_back(u,i);
    }
    void dfs(int u,int fr)
    {
        dfn[u]=low[u]=++cnt;
        int child=0,time=0;
        for(auto [v,i]:g[u])
        {
            if(v==fr&&time==0)
            {
                time++;
                continue;
            }
            if(!dfn[v])
            {
                child++;
                dfs(v,u);
            }
            if(u==fr&&child>=2)
                point[u]=1;
            if(u!=fr&&low[v]>=dfn[u]&&child>=1)
                point[u]=1;
            if(low[v]>dfn[u])
                bridges.push_back(i);
            low[u]=min(low[u],low[v]);
        }
    }
    void solve()
    {
        for(int i=0;i 
强连通分量  c++98
 
struct scc{
    const int nn;
    int cnt,idx;
    vector col,dfn,low,stk;
    vector onstk;
    vector > g,comp;
    scc(int n1):nn(n1),cnt(0),idx(0),col(n1),dfn(n1,0),low(n1),stk(n1),onstk(n1,0),g(n1){}
    void add_edge(int u,int v)
    {
        g[u].push_back(v);
    }
    void dfs(int u)
    {
        dfn[u]=low[u]=++cnt;
        stk[idx++]=u;
        onstk[u]=true;
        for(int i=0;i a1;
            while(true)
            {
                int v=stk[--idx];
                onstk[v]=false;
                a1.push_back(v);
                if(u==v) 
                    break;
            }
            comp.push_back(a1);
        }
    }
    void solve()
    {
        for(int i=0;i