CF1594 D. The Number of Imposters（扩展域并查集）

Description

State

Input

Output

Solution

Code

Description

有 \(n\) 个人，\(x\ y \ c/i\) 表示 \(x\) 说 \(y\) 是船员，或者是叛徒，最多可以有多少船员；

船员一定说真话，叛徒一定说假话

Alice 围观了一场 ICPC 竞赛的滚榜环节。本次竞赛共有 $n$ 支队伍参赛，队伍从 $1～n$ 编号，$i$ 号队伍在封榜前通过的题数为 $a_i$。排行榜上队伍按照过题数从大到小进行排名，若两支队伍过题数相同，则编号小的队伍排名靠前。

State

\(1<=n<=2*10^5\)

\(1<=m<=5*10^5\)

Input

5
3 2
1 2 imposter
2 3 crewmate
5 4
1 3 crewmate
2 5 crewmate
2 4 imposter
3 4 imposter
2 2
1 2 imposter
2 1 crewmate
3 5
1 2 imposter
1 2 imposter
3 2 crewmate
3 2 crewmate
1 3 imposter
5 0

Output

2
4
-1
2
5

Solution

如果 \(x\) 说 \(y\) 是船员，那么他们是一种身份，否则他们拥有不同的身份，那么只有同类合并与异类合并两种

以 \(i\) 表示其为船员， \(i+n\) 表示其为叛徒

在合并的过程会出现认贼作父的情况，所以最后取贡献为 \(max(sz[i],sz[Find(i+n)])\)

Code

const int N = 4e5 + 5;

    int n, m, k, _;
    int a[N];
    int fa[N], sz[N];

int Find(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = Find(fa[x]);
}

void Union(int x, int y)
{
    int nx = Find(x), ny = Find(y);
    if(nx != ny){
        fa[nx] = ny;
        sz[ny] += sz[nx];
        sz[nx] = 0;
    }
}

signed main()
{
    // IOS;
    rush(){
        sdd(n, m);
        rep(i, 1, n){
            fa[i] = i;
            sz[i] = 1;
        }
        rep(i, n + 1, n + n){
            fa[i] = i;
            sz[i] = 0;
        }
        int ok = 1;
        while(m --> 0){
            int x, y;
            char s[10];
            sdd(x, y);
            ss(s);
            if(s[0] == 'c'){
                if(Find(x) == Find(y + n) || Find(y) == Find(x + n)) ok = 0;
                Union(x, y);
                Union(x + n, y + n);
            }
            else{
                if(Find(x + n) == Find(y + n) || Find(x) == Find(y)) ok = 0;
                Union(x + n, y);
                Union(x, y + n);
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            if(Find(i) == i) ans += max(sz[i], sz[Find(i + n)]);
        }
        if(ok == 0) ans = -1;
        pd(ans);
    }
    return 0;
}