UVALive - 4288 Cat vs. Dog(最大独力集)

题目大意：给出N个人的投票，每个人投票形式为以下两种的其中一种
1.喜欢的狗的编号，讨厌的猫的编号
2.喜欢的猫的编号，讨厌的狗的编号
问如何选择猫狗，才能满足最多的人的投票

解题思路：找出每个喜欢猫的人和喜欢狗的人，然后分成两个点集
如果喜欢的猫和对方讨厌的猫相同，或者讨厌的狗和对方喜欢的狗相同，那么就表示这两个人的愿望是无法同时满足的了，那么连线
接下来，最大独立集就是那些人的愿望都能满足的了

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define N 510

struct voter{
    char a[5], b[5];
}cat[N], dog[N];

int c, d, v,  cat_cnt, dog_cnt;
int link[N];
char love[5], hate[5];
bool vis[N];
vector<int> G[N];
void init() {
    scanf("%d%d%d", &c, &d, &v);
    cat_cnt = dog_cnt = 0;
    for (int i = 0; i < v; i++) {
        scanf("%s%s", love, hate);
        if (love[0] == 'C') {
            strcpy(cat[cat_cnt].a, love);
            strcpy(cat[cat_cnt].b, hate);
            G[cat_cnt++].clear();
        }
        else {
            strcpy(dog[dog_cnt].a, love);
            strcpy(dog[dog_cnt++].b, hate);
        }
    }

    for (int i = 0; i < cat_cnt; i++)
        for (int j = 0; j < dog_cnt; j++) 
            if (!strcmp(cat[i].a, dog[j].b) || !strcmp(cat[i].b, dog[j].a))
                G[i].push_back(j);
}

bool dfs(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (!(~link[v]) || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    int cnt = 0;
    memset(link, -1, sizeof(link));
    for (int i = 0; i < cat_cnt; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
            cnt++;
    }
    printf("%d\n", v - cnt);
}

int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}