CodeForces - 1445E Team-Building

传送门：CodeForces - 1445E

思路分析

每次选两种颜色的点，判断子图是否构成二分图，暴力枚举子图肯定不行，考虑减去非法方案

1. 如果存在一个奇环且环上只有一钟颜色，那么所有与该颜色的组合方法都不行
2. 如果存在一个奇环且环上只有两种颜色，那么该种组合方案不行

对于第一种情况，用并查集判断
对于第二种情况，之前判断第一种的时候已经将所有相同颜色的点连成连通块，只需要再加入另一种颜色点，考虑将边进行分类，每算出一种不合法方案的时候，撤销掉该点的影响

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int N = 1e6+10;

struct undo_dsu {
    stack<pii>st;
    int n;
    vector<int>f,siz;
    undo_dsu(int nn) {
        n = nn;
        while(!st.empty()) st.pop();
        f.resize(n+2);
        siz.resize(n+2);
        for(int i=1; i<=n; i++) f[i] = i,siz[i] = 1;
    }

    int find(int x) {
        return x == f[x] ? x:find(f[x]);
    }

    bool merge(int x,int y) {
        int fx = find(x) , fy = find(y);
        if(fx == fy) return false;
        if(siz[fx] > siz[fy]) {
            swap(fx,fy);
            swap(x,y);
        }
        f[fx] = fy;
        siz[fy] += siz[fx];
        st.push(mp(fx,fy));
        return true;
    }

    void undo() {
        if(st.empty()) return ;
        pii now = st.top();
        st.pop();
        int fx = now.fi , fy = now.se;
        f[fx] = fx;
        siz[fy] -= siz[fx];
    }

};

int c[N],a[N],b[N],vis[N];
map<pii,vector<int>>q;


int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m,k;
    cin>>n>>m>>k;
    undo_dsu dsu(n*2+2);
    for(int i=1; i<=n; i++) cin>>c[i];
    for(int i=1; i<=m; i++) cin>>a[i]>>b[i];
    for(int i=1; i<=m; i++) {
        if(c[a[i]] == c[b[i]]) {
            int fx = dsu.find(a[i]) , fy = dsu.find(b[i]);
            if(fx == fy) vis[c[a[i]]] = 1;
            else dsu.merge(a[i],b[i]+n) , dsu.merge(b[i],a[i]+n);
        }
    }
    for(int i=1;i<=m;i++){
        if(c[a[i]] != c[b[i]] && !vis[c[a[i]]] && !vis[c[b[i]]]){
            int lc = c[a[i]] , rc = c[b[i]];
            if(lc>rc) swap(lc,rc);
            q[mp(lc,rc)].pb(i);
        }
    }
    ll ans = 0;
    for(auto type:q){
        int pre = sz(dsu.st);
        for(auto i:type.se){
            int x = a[i] , y = b[i];
            int fx = dsu.find(x) , fy = dsu.find(y);
            if(fx == fy){
                ans--;
                break;
            }
            dsu.merge(x,y+n);
            dsu.merge(y,x+n);
        }
        while(sz(dsu.st)>pre) dsu.undo();
    }
    
    ll cnt = 0;
    for(int i=1;i<=k;i++) if(!vis[i]) cnt++;
    ans = (ans + cnt*(cnt-1)/2);
    cout<<ans<<endl;




    return 0;
}