题目描述

消息传递接口
和yxc 的方法不同之处在于 给每个queue最后加了一个 oprator{-1,-1} 表示结束 而没有使用虚拟的-1 进程
也算是一种思路

C++ 代码

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<sstream>

using namespace std;

const int N = 10010;

struct Op{

    int p;
    int id;

};
queue<Op> op[N];

bool st[N];

bool dfs(int opr , int id, int pid, int die)   // opr  要求的操作 ， id 接收者  pid 发送者  die  爹， 也就是最初发起这轮操作的那个进程
{
    if(st[id] == true) return false;

    if(id == -1 && pid == die)
    return true;  // 这个进程已经走完了
    else if( id == -1)
    return false;

    st[id] = true;


    while(!op[id].empty())
    {
        Op opt = op[id].front();
        op[id].pop();

        if(opt.p == opr && opt.id == pid)
        {
            st[id] = false;
            return true;
        }
        else if(dfs(opt.p^1 , opt.id , id, die)) continue;
        else 
        return false;
    }



}



int t,n;
int main()
{
    cin>>t>>n;
    getchar();
    while(t--)
    {


        for(int i=0;i<n;i++)
        {
            op[i] = queue<Op>(); // clear the i th  queue
            st[i] = false;

            // use the stream to output every word splited by " " (space)
            string s;
            getline(cin,s);
            string str;
            stringstream ssin(s);


            while(ssin>>str)// iterate every string splited by " "
            {
                if(str[0] == 'S') op[i].push({0, stoi(str.substr(1))});
                else
                op[i].push({1,stoi(str.substr(1))});
            }

            op[i].push({-1,-1});
        }

        bool success;
        for(int i=0;i<n;i++)
        {
            bool res_now;
            while(!op[i].empty())
            {
                Op opt = op[i].front();
                op[i].pop();
                st[i] = true;
                res_now = dfs(opt.p^1,opt.id, i, i);
                if(!res_now)
                {
                    cout<<1<<endl;
                    break;
                }
            }

            success = true;;
            if(!res_now) 
            {
                success = false;
                break;
            }

        }
        if(success)
        cout<<0<<endl;

    }

    return 0;
}