题目地址:http://poj.org/problem?id=1703

题目大意

一个城市里有两个罪犯帮派,每个罪犯必在其中的一个帮派,现在给出一些消息,$D a b$表示已知$a, b$两人不同帮派,问$A a b$即$a, b$两人的信息?

思路

以前做过一道类似的,刚刚看了下博客,和杭电那道极其相似(A Bug’s life),但是写起来还是各种问题,比如各种卡时间,卡内存。。

首先要一个opp数组以标记$x, y$的对立信息,然后就好办了。。

之前判断”Not sure yet.”这个条件的时候,用的是visited数组标记已知信息$D a b$中的$a, b$,然后如果询问的时候如果两个不都是visited过的话,就判”Not sure yet.“,一直WA。。。理由:比如已知(1, 2)对立,(3,4)对立,(1,4)已经标记过了,但是无法确定。。具体可看注释代码。。
=======================2015-11-10更新===========================
做了一题食物链,感觉之前的写法太粗暴了,现在感觉有个通用解法。。具体看AC代码2

AC代码

/*************************************************************************
    > File Name: 1703.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-09 一 20:11:57 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int T, N, M;
int par[100005];
int opp[100005]; // 记录罪犯i的对立帮派
bool visited[100005];

void init(){
    for(int i=1; i<=N; ++i) {
        par[i] = i;
    }
}

int find(int x) {
    return x==par[x]?x:par[x]=find(par[x]); // 这里可能爆栈233
}
int same(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    x=find(x);
    y=find(y);
    if(x == y) return;
    par[x] = y;
}

void solve() {
    memset(opp, 0, sizeof(opp));
    memset(visited, 0, sizeof(visited));
    init();

    char op;
    int x, y;

    while(M--) {
        scanf("%c%d%d", &op, &x, &y);
        getchar();
        if(op == 'A') {
            // if(visited[x] && visited[y]) {
                // if(same(x, y)) printf("In the same gang.\n"); // 同帮派
                // else if(same(x, opp[y])) printf("In different gangs.\n"); // x和y的对立面同一党派,那么x和y不同帮派
            // }
            // else printf("Not sure yet.\n");
            if(same(x, y)) printf("In the same gang.\n"); // 同帮派
            else if(same(x, opp[y])) printf("In different gangs.\n"); // x和y的对立面同一党派,那么x和y不同帮派
            else printf("Not sure yet.\n");
        }
        else {
            // 之前对立帮派
            if(opp[x]) unite(y, opp[x]); // 因为y和x对立,x和opp[x]对立,那么opp[x]和y则相同帮派
            if(opp[y]) unite(x, opp[y]);
            // 之后更新对立帮派
            opp[x] = y;
            opp[y] = x;
            // visited[x] = visited[y] = true;
        }
    }

}

int main()
{
#ifdef Oj
    freopen("1703.in", "r", stdin);
#endif
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &N, &M);
        getchar();
        solve();
    }
    return 0;
}

AC代码2

/*************************************************************************
    > File Name: 1703_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-10 一 20:11:57 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int T, N, M;
int par[100005*2]; // i-x表示i属于x,x={Gang Dragon, Gang Snake}

void init(){
    for(int i=1; i<=N*2; ++i) {
        par[i] = i;
    }
}

int find(int x) {
    return x==par[x]?x:par[x]=find(par[x]); // 这里可能爆栈233
}
int same(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    x=find(x);
    y=find(y);
    if(x == y) return;
    par[x] = y;
}

void solve() {
    init();

    char op;
    int x, y;

    while(M--) {
        scanf("%c%d%d", &op, &x, &y);
        getchar();
        if(op == 'A') {
            if(same(x, y))
                printf("In the same gang.\n");
            else if(same(x, y+N))
                printf("In different gangs.\n");
            else
                printf("Not sure yet.\n");
        }
        else {
            unite(x, y+N);
            unite(x+N, y);
        }
    }

}

int main()
{
#ifdef Oj
    freopen("1703.in", "r", stdin);
#endif
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &N, &M);
        getchar();
        solve();
    }
    return 0;
}