2018-ACetic_ACid/AugTrain-06/G

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
#ifdef LOCAL
#define debug 1
#else
#define debug 0
#endif

typedef long long ll;
using namespace std;
#define N 220000
int T,n,m;
int fir[N],nes[N<<1],v[N<<1],tot=1;
int jsq,sta[N],top=0,st,ed,pos[N],ring[N<<1],tmp1,tmp2;
bool Judge,mark[N],fz[N<<1];
int b[N];
vector<int> V[N];
void edge(int x,int y)
{
    v[++tot]=y;
    nes[tot]=fir[x];
    fir[x]=tot;
}
void Edge(int x,int y)
{
    edge(x,y);
    edge(y,x);
}
void init()
{
    for(int i=0;i<=tot;i++) fz[i]=false,ring[i]=false;
    for(int i=1;i<=n;i++) fir[i]=0,mark[i]=false,b[i]=0;
    tot=1;
    top=0;
    jsq=0;
    Judge=false;
}
void dfs(int c)
{
    mark[c]=true;
    for(int t=fir[c];t;t=nes[t])
    {
        if(fz[t]) continue;
        fz[t]=fz[t^1]=true;
        if(mark[v[t]])
        {
            sta[++top]=t; fz[t]=fz[t^1]=true;
            jsq++; V[jsq].clear();
            for(int i=pos[v[t]]+1;i<=top;i++)
            {
                if(ring[sta[i]] && !Judge)
                {
                    st=v[sta[i]^1]; Judge=true;
                    tmp1=ring[sta[i]];
                    tmp2=jsq;
                }
                ring[sta[i]]=jsq;
                V[jsq].push_back(v[sta[i]]);
            }
            top--;
            if(Judge) return;
            continue;
        }
        sta[++top]=t;
        pos[v[t]]=top;
        dfs(v[t]);
        if(Judge) return;
        top--;
    }
}
int main()
{
    freopen("grand.in","r",stdin);
    freopen("grand.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            Edge(x,y);
        }
        for(int i=1;i<=n;i++)
        {
            if(!mark[i])
                        {
                                pos[i]=0;//<-就只改了这行
                    dfs(i);
                        }
            if(Judge) break;
        }
        if(!Judge) { printf("-1\n"); continue; }
        int i=0,j=0;
        int st1,st2,ed1,ed2;
        while(V[tmp1][i]!=st && i<V[tmp1].size()) i++;
        if(i==V[tmp1].size())
        {
            printf("-1\n");
            continue;
        }
        st1=i;
        while(V[tmp2][j]!=st && j<V[tmp2].size()) j++;
        if(j==V[tmp2].size())
        {
            printf("-1\n");
            continue;
        }
        st2=j;
        int cnt1=0;
        while(V[tmp1][i]==V[tmp2][j])
        {
            i++;
            if(i==V[tmp1].size()) i=0;
            j++;
            if(j==V[tmp2].size()) j=0;
            cnt1++;
        }
        ed=V[tmp1][(i==0?(V[tmp1].size()-1):(i-1))];
        printf("%d %d\n",st,ed);
        printf("%d",cnt1);
        for(i=st1;V[tmp1][i]!=ed;i=((i+1)==V[tmp1].size()?0:(i+1)))
        {
            printf(" %d",V[tmp1][i]);
        }
        printf(" %d\n",ed);
        printf("%d",V[tmp1].size()-cnt1+2);
        for(i=st1;V[tmp1][i]!=ed;i=((i==0)?(V[tmp1].size()-1):(i-1)))
        {
            printf(" %d",V[tmp1][i]);
        }
        printf(" %d\n",ed);
        printf("%d",V[tmp2].size()-cnt1+2);
        for(i=st2;V[tmp2][i]!=ed;i=((i==0)?(V[tmp2].size()-1):(i-1)))
        {
            printf(" %d",V[tmp2][i]);
        }
        printf(" %d\n",ed);
    }
    return 0;
}

}}}

#include <bits/stdc++.h>
#ifdef LOCAL
#define debug 1
#else
#define debug 0
#endif
typedef long long ll;
using namespace std;
#define N 220000
int T,n,m;
int fir[N],nes[N<<1],v[N<<1],tot=1;
int jsq,sta[N],top=0,st,ed,pos[N],ring[N<<1],tmp1,tmp2;
bool Judge,mark[N],fz[N<<1];
int b[N];
vector<int> V[N];
void edge(int x,int y)
{
    v[++tot]=y;
    nes[tot]=fir[x];
    fir[x]=tot;
}
void Edge(int x,int y)
{
    edge(x,y);
    edge(y,x);
}
void init()
{
    for(int i=0;i<=tot;i++) fz[i]=false,ring[i]=false;
    for(int i=1;i<=n;i++) fir[i]=0,mark[i]=false,b[i]=0;
    tot=1;
    top=0;
    jsq=0;
    Judge=false;
}
void dfs(int c)
{
    mark[c]=true;
    for(int t=fir[c];t;t=nes[t])
    {
        if(fz[t]) continue;
        fz[t]=fz[t^1]=true;
        if(mark[v[t]])
        {
            sta[++top]=t; fz[t]=fz[t^1]=true;
            jsq++; V[jsq].clear();
            for(int i=pos[v[t]]+1;i<=top;i++)
            {
                if(ring[sta[i]] && !Judge)
                {
                    st=v[sta[i]^1]; Judge=true;
                    tmp1=ring[sta[i]];
                    tmp2=jsq;
                }
                ring[sta[i]]=jsq;
                V[jsq].push_back(v[sta[i]]);
            }
            top--;
            if(Judge) return;
            continue;
        }
        sta[++top]=t;
        pos[v[t]]=top;
        dfs(v[t]);
        if(Judge) return;
        top--;
    }
}
int main()
{
    freopen("grand.in","r",stdin);
    freopen("grand.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1,x,y;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            Edge(x,y);
        }
        for(int i=1;i<=n;i++)
        {
            if(!mark[i])
                        {
                                pos[i]=0;//<-就只改了这行
                    dfs(i);
                        }
            if(Judge) break;
        }
        if(!Judge) { printf("-1\n"); continue; }
        int i=0,j=0;
        int st1,st2,ed1,ed2;
        while(V[tmp1][i]!=st && i<V[tmp1].size()) i++;
        if(i==V[tmp1].size())
        {
            printf("-1\n");
            continue;
        }
        st1=i;
        while(V[tmp2][j]!=st && j<V[tmp2].size()) j++;
        if(j==V[tmp2].size())
        {
            printf("-1\n");
            continue;
        }
        st2=j;
        int cnt1=0;
        while(V[tmp1][i]==V[tmp2][j])
        {
            i++;
            if(i==V[tmp1].size()) i=0;
            j++;
            if(j==V[tmp2].size()) j=0;
            cnt1++;
        }
        ed=V[tmp1][(i==0?(V[tmp1].size()-1):(i-1))];
        printf("%d %d\n",st,ed);
        printf("%d",cnt1);
        for(i=st1;V[tmp1][i]!=ed;i=((i+1)==V[tmp1].size()?0:(i+1)))
        {
            printf(" %d",V[tmp1][i]);
        }
        printf(" %d\n",ed);
        printf("%d",V[tmp1].size()-cnt1+2);
        for(i=st1;V[tmp1][i]!=ed;i=((i==0)?(V[tmp1].size()-1):(i-1)))
        {
            printf(" %d",V[tmp1][i]);
        }
        printf(" %d\n",ed);
        printf("%d",V[tmp2].size()-cnt1+2);
        for(i=st2;V[tmp2][i]!=ed;i=((i==0)?(V[tmp2].size()-1):(i-1)))
        {
            printf(" %d",V[tmp2][i]);
        }
        printf(" %d\n",ed);
    }
    return 0;
}