2016ACMICPC亚洲区大连站重现赛1001 Wrestling Match-蒲公英云

2016ACMICPC亚洲区大连站重现赛1001 Wrestling Match

菜鸟写题，多多指教

HDU 5971Wrestling Match

题意：n(<=1000)个人，其中有个x好人，y个坏人m(<=10000)场比赛，胜者为好人，负者为坏人

问能通过这些比赛是否可能将所有人分为好人或坏人。也就是每个人都有一状态，并且和比赛不冲突；

//输入

n m x y

5 4 1 0

//对手，也就是关系

a b

1 3

1 4

3 5

4 5

//x个好人的列表

//y个坏人的列表

//输出

YES

遍历所有相关集，所有集合都满足 (状态不冲突，所有人有状态) 则输出YES；

遍历参数是相关集，每个集合最多两种情况，

确定一个人可以确定相关集里的所有人；

vector c[1010]存关系；

int a[1010] 存状态；

set s[1010]存集合

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x,y;
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)
    {
        vector<int> c[1010];//关系
        int ac[1010];//状态,ac[0]不存
        memset(ac,0,sizeof(ac));
        int k = 0;//集合数
        set<int> s[1010];
        for(int ii = 0; ii < m; ii++){
            int a,b;
            scanf("%d%d",&a,&b);
            c[a].push_back(b);
            c[b].push_back(a);
            int ka = 0,kb = 0;//a,b所在集合，没有为0；
            for(int i = 1; i <= k; i++){
                if(s[i].find(a)!= s[i].end()) ka = i;
                if(s[i].find(b)!= s[i].end()) kb = i;
            }
            if(!ka && !kb){     //a,b都没有所属集合
                k++;
                s[k].insert(a);
                s[k].insert(b);
            }
            else if(!ka)  //a没有所属集合
                s[kb].insert(a);
            else if(!kb)    //b没有
                s[ka].insert(b);
            else if(ka != kb){  //a,b都有，合并两集合并s[ka]标记为无效
                if(s[ka].size() > s[kb].size()) swap(ka,kb);
                set<int>::iterator it;
                for(it = s[ka].begin(); it != s[ka].end(); it++)
                    s[kb].insert(*it);
                s[ka].clear();
                s[ka].insert(-10);
            }
        }
        /*
        for(int i = 1; i <= k; i++)//print all sets
        {
            cout<<i<<":  ";
            for(set<int>::iterator it = s[i].begin(); it != s[i].end(); it++)
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
        */
        for(int i = 0; i < x; i++)
        {
            int a;
            scanf("%d",&a);
            ac[a] = 1;
        }
        for(int i = 0; i < y; i++)
        {
            int a;
            scanf("%d", &a);
            ac[a] = -1;
        }
        //cout<<k<<endl;
        int ok = 1;
        for(int i = 1; i <= k; i++)///visit sets;
        {
            set<int>::iterator it = s[i].begin();
            if(*it == -10) continue;
            for(it; it != s[i].end(); it++)
            {
                if(ac[*it]) break;
            }
            if(it == s[i].end())//集合中没有已经确定的元素；假设一种状态
            {
                it = s[i].begin();
                ac[*it] = 1;
                //cout<<*it<<"  "<<i<<"  "<< -ac[*it]<<"  **"<<endl;
            }
            int tip[1010]; //是否已经被访问不能仅从ac[] == 0来判断
            memset(tip,0,sizeof(tip));
            queue<int> q;
            q.push(*it);
            while(!q.empty())
            {
                int q1 = q.front();
                q.pop();
                if(tip[q1]) continue;
                else tip[q1] = 1;
                for(int i = 0; i < c[q1].size(); i++)
                {
                    if(!ac[c[q1][i]])//对手没有性质
                    {
                        ac[c[q1][i]] = -ac[q1];
                        q.push(c[q1][i]);
                    }
                    else if(ac[c[q1][i]] == ac[q1])
                    {
                        ok = 0;  //对手和自己性质相同
                        //cout<<q1<<" == "<<c[q1][i]<<endl;
                        break;
                    }
                    else
                    {
                        q.push(c[q1][i]);
                    }
                }
                if(!ok) break; //已经违反，不再进行循环
            }
        }
        for(int i = 1; i <= n; i++)
        {
            //cout<<ac[i]<<"   x"<<endl;
            if(!ac[i])
            {
                ok = 0;
                //break;
            }
        }
        if(ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;;
    }
    return 0;
}