tarjan 输出0 求调

hzoi_Shadow @ 2023-07-15 16:50:04

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
struct node
{
    int next,to;
}e[4000001];
vector<int>e_dcc[4000001];
stack<int>s;
int head[4000001],dfn[4000001],low[4000001],cnt=0,tot=0,ans=0;
void add(int u,int v)
{
    cnt++;
    e[cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void tarjan(int x,int fa)
{
    int i,k=0,pd=0;
    tot++;
    dfn[x]=low[x]=tot;
    s.push(x);
    for(i=head[x];i!=0;i=e[i].next)
    {
        if(dfn[e[i].to]==0)
        {
            tarjan(e[i].to,x);
            low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]>dfn[x])
            {
                ans++;
                while(e[i].to!=k)
                {
                    k=s.top();
                    e_dcc[ans].push_back(k);
                    s.pop();
                }   
            }
        }
        else
        {
            if(e[i].to==fa&&pd==0)
            {
                pd=1;
            }
            else
            {
                low[x]=min(low[x],dfn[e[i].to]);
            }
        }
    }
}
int main()
{
    int n,m,i,j,u,v;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        if(u!=v)
        {
            add(u,v);
            add(v,u);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            tarjan(i,i);
        }
    }
    cout<<ans<<endl;
    for(i=1;i<=ans;i++)
    {
        cout<<e_dcc[i].size()<<" ";
        for(j=0;j<e_dcc[i].size();j++)
        {
            cout<<e_dcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}·

by hzoi_Shadow @ 2023-07-15 16:50:16

@The_Shadow_Dragon 求割边的部分，能过P1656

by hzoi_Shadow @ 2023-07-15 17:36:26

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
struct node
{
    int next,to,flag;
}e[4000001];
vector<int>e_dcc[4000001];
int head[4000001],dfn[4000001],low[4000001],flag[4000001],vis[4000001],cnt=1,tot=0,ans=0;
void add(int u,int v)
{
    cnt++;
    e[cnt].next=head[u];
    e[cnt].flag=0;
    e[cnt].to=v;
    head[u]=cnt;
}
void tarjan(int x,int fa)
{
    int i;
    tot++;
    dfn[x]=low[x]=tot;
    for(i=head[x];i!=0;i=e[i].next)
    {
        if(dfn[e[i].to]==0)
        {
            tarjan(e[i].to,i);
            low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]>dfn[x])
            {
                e[i].flag=e[i^1].flag=1;
            }
        }
        else
        {
            if((fa^1)!=i)
            {
                low[x]=min(low[x],dfn[e[i].to]);
            }
        }
    }
}
void dfs(int x)
{
    e_dcc[ans].push_back(x);
    vis[x]=1;
    for(int i=head[x];i!=0;i=e[i].next)
    {
        if(vis[e[i].to]==0&&e[i].flag==0)
        {
            dfs(e[i].to);
        }
    }
}
int main()
{
    int n,m,i,j,u,v;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        //if(u!=v)
        //{
            add(u,v);
            add(v,u);
        //}
    }
    for(i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            tarjan(i,0);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            ans++;
            dfs(i);
        }
    }
    cout<<ans<<endl;
    for(i=1;i<=ans;i++)
    {
        cout<<e_dcc[i].size()<<" ";
        for(j=0;j<e_dcc[i].size();j++)
        {
            cout<<e_dcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}