随机算法

mt19937 sd;
struct Rand_Match
{
    int match[N],vis[N];
    vector<int> G[N];
    void add(int x,int y)
    {
        G[x].pb(y);
        G[y].pb(x);
    }
    int dfs(int x,mt19937 sd)
    {
        shuffle(G[x].begin(),G[x].end(),sd);
        vis[x] = 1;
        for(auto y: G[x])
            if(!match[y]) return vis[y] = 1,match[y] = x,match[x] =y,1;
        for(auto y: G[x])
        {
            int z = match[y];
            if(vis[z]) continue;
            match[x] = y,match[y] = x,match[z] = 0;
            if(dfs(z,sd)) return 1;
            match[y] = z,match[z] = y,match[x] = 0;
        }
        return 0;
    }
    void run(int n)
    {
        random_device seed;
        mt19937 sd(seed());
        int ans = 0;
        MM(match,0);
        FOR(k,1,10)
        {
            FOR(i,1,n)
                if(G[i].size() && !match[i])
                {
                    fill(vis + 1, vis + 1 + n, 0);
                    ans += dfs(i,sd);
                }
            if(ans == n/2) break;
        }
//        PLN(ans);
        if(ans == n/2) PS("Yes");
        else PS("No");
        FOR(i,1,n) G[i].clear();
    }
}O_O;