题解：P5937 [CEOI1999] Parity Game

rainbow_cat · 2025-01-08 20:09:32 · 题解

为什么都用并查集呢，提供一种二分图的写法，定义前缀和数组 s_1,s_2,\dots,s_n。
若 x 到 y 为 even 则 s_y 与 s_{x-1} 奇偶相同，否则不同。
使用二分图的常见技巧，若相同，将两个点连接到一个虚点上，否则直接相连，每连一次边跑一次二分图染色，判断是否可行即可。
由于值域过大，需要离散化。

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,idx,mpidx,col[20010];
bool flag,vis[20010];
string s;
map<int,int>mp;
vector<int>e[20010];
void dfs(int u)
{
    vis[u]=1;
    for(auto i:e[u])
    {
        if(vis[i]&&col[i]==col[u])flag=1;
        else if(!vis[i])col[i]=col[u]^1,vis[i]=1,dfs(i);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    idx=m;
    for(int i=1;i<=m;i++)
    {
        flag=0;
        cin>>x>>y>>s;
        if(!mp[x-1])mp[x-1]=++mpidx;
        if(!mp[y])mp[y]=++mpidx;
        if(s=="even")
        {           
            e[mp[x-1]].push_back(2*m+(++idx)),e[2*m+idx].push_back(mp[x-1]);
            e[2*m+idx].push_back(mp[y]),e[mp[y]].push_back(2*m+idx);
        }
        else e[mp[x-1]].push_back(mp[y]),e[mp[y]].push_back(mp[x-1]);
        for(int j=1;j<=mpidx;j++)vis[j]=col[j]=0;
        for(int j=2*m+1;j<=2*m+idx;j++)vis[j]=col[j]=0;
        for(int j=1;j<=mpidx;j++)
        {
            if(vis[j])continue;
            dfs(j);
            if(flag)
            {
                cout<<i-1;
                return 0;
            }
        }
        for(int j=2*m+1;j<=2*m+idx;j++)
        {
            if(vis[j])continue;
            dfs(j);
            if(flag)
            {
                cout<<i-1;
                return 0;
            }
        }
    }
    cout<<m;
    return 0;
}