”赛码杯“ Exploration

#include <iostream>
#include <stdio.h>
#include <vector>
#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

bool visit[1000010],flag[1000010],USE[2000010];
int x[2000010],y[2000010],NEXT[3000010],value[3000010],h[1000010];
int n,m1,m2,top;
bool success;

void addedge(int u, int v)
{
    ++top;
    NEXT[top]=h[u];
    value[top]=v;
    h[u]=top;
}

void DFS(int k)
{
    if (success) return;
    visit[k]=true;
    int q=h[k];

    while(q!=-1)
    {
        int u=value[q],to;
        if (USE[u])
        {
            q=NEXT[q];
            continue;
        }
        if (x[u]==k) to=y[u]; else to=x[u];
        if (flag[to])
        {
            success=true;
            return;
        }
        if (visit[to])
        {
            q=NEXT[q];
            continue;
        }

        flag[to]=true;
        USE[u]=true;
        DFS(to);
        flag[to]=false;
        USE[u]=false;
        q=NEXT[q];
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m1,&m2);
        top=0;
        for (int i=1;i<=n;i++)
        {
            visit[i]=false;
            h[i]=-1;
        }

        for (int i=1;i<=m1;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            addedge(x[i],i);
            addedge(y[i],i);
        }

        for (int i=m1+1;i<=m1+m2;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            addedge(x[i],i);
        }

        success=false;
        for (int i=1;i<=n;i++)
        {
            flag[i]=true;
            if (!visit[i]) DFS(i);
            flag[i]=false;
            if (success)
            {
                printf("YES\n");
                break;
            }
        }
        if (!success)
        {
            printf("NO\n");
        }
    }
    return 0;
}