BAPC preliminaries2016 B题 Chess Tournament 并查集+拓扑排序

曾经终败给现在 2022-11-29 03:20 27阅读 0赞

[原题链接：B：Chess Tournament][B_Chess Tournament]

#### 题目背景 ####

> Your friend is an organizer of the International Chess Playing Championship. He is worried that some of the contestants may be cheating, and he has asked you to help out. The chess players are allowed to report matches to the jury themselves, and this is not checked with the reported opponent. So, it is possible for competitors to make up matches and falsely report themselves as the winners. Since chess is a game of skill, and not of chance, a player will always beat their opponent if their skill leves higher. A game will result in a draw if and only if the two players’ skills are exactly equal. However, the skill level of the players is not known. He has therefore asked you to write a program that, given a list of reported matches, determines whether this list is consistent or not. The list is inconsistent if we can determine that at least one reported match is falsely reported, otherwise it is consistent.

#### Input ####

> The first line contains two integers N (2≤N≤500002≤N≤50000) and M (1≤M≤2500001≤M≤250000), to describe a championship with N players and M reported matches.The following M lines each consist of an integer K, a symbol which is either ‘=’ or ‘>’, and another integer L. The integers K and L each uniquely identify a player (0≤K,L<N，0≤K,L<N). If the symbol is ‘=’, then the game between KK and L was a draw. If the symbol is ‘>’, then K beat L in a match. You may assume that there is at most one reported match between any given pair of players. Also, each player takes part in at least one reported match.

#### Output ####

> Output a single line containing a single word: “consistent” if the list of recorded matches is consistent, and “inconsistent” if it is not.

样例

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center]

#### 题目大意 ####

题目说会有n个人，m个下棋水平的关系，每两个人的水平有 ‘=’ 关系，即两个人水平相等，也有 ‘<’ 和 ‘>’ 关系，即存在水平的高低。现在要判断给你的m个关系是否合理。

#### 思路 ####

看到样例，思路很清晰，就是输入m个水平关系后，判断是否有冲突即可。但是实现起来又不一样。关键是如何处理并判断两人间的关系是否冲突呢。这里我们很容易 想到对于=关系我们用[**并查集**][Link 1]合并，对于<和>关系用有向边建立联系，最后用[**拓扑排序**][Link 2]判断是否冲突，返回答案即可。  
但是这里建立有向边时一定要注意是对这两个人的祖先建边。之前我们对所有有=关系的人用并查集处理到了同一个集合里。所以我们就需要对**集合**之间建边，判断**集合**之间是否冲突。而我们对其并查集的祖先建边，就相当于对于集合之间建边。

#### 代码解析 ####

#include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    const int N = 50010;
    struct node{ 		//存输入的两人间的关系
    	int a,b;	//两个人的序号
    	char op;	//关系符号
    };
    
    int n,m,fa[N],d[N],cnt,sum;	//fa并查集的祖先数组，d拓扑的入度，cnt计算集合数量，sum计算拓扑序的个数
    bool flag = 1;		//标记
    vector<node> arr;	//存所有的两人关系
    vector<int> es[N];	//建立有向边
    queue<int> q;		//拓扑的队列
    
    int find(int n)		//查
    { 
    	if(fa[n] == n)
    		return n;
    	return fa[n] = find(fa[n]);
    }
    
    void un(int a,int b)	//并
    { 
    	fa[find(a)] = fa[find(b)];
    }
    
    void topsort()		//拓扑排序
    { 
    	for(int i = 0;i < n;i++)	//注意输入的序号是0到n-1
    		if(d[i] == 0 && fa[i] == i)	//如果入度为0且自己是祖先
    			q.push(i);	//入队
    	while(!q.empty())
    	{ 
    		int u = q.front();
    		q.pop();
    		sum++;
    		for(int i = 0;i < es[u].size();i++)
    		{ 
    			int v = es[u][i];
    			d[v]--;
    			if(!d[v])
    				q.push(v);
    		}
    	}	
    }
    
    int main()
    { 
    	int a,b;
    	char t;
    	cin >> n >> m;
    	for(int i = 0;i <= n;i++)	//并查集的初始化
    		fa[i] = i;
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> t >> b;
    		arr.push_back({ a,b,t});	//存进arr数组
    		if(t == '=')
    			un(a,b);	//如果是 =，合并
    	}
    	for(int i = 0;i < n;i++)
    		if(fa[i] == i)
    			cnt++;		//cnt计算所有集合数量，即祖先数量
    
    	for(int i = 0;i < m;i++)
    	{ 
    		if(arr[i].op != '=')
    		{ 
    			int u = arr[i].a,v = arr[i].b;
    			char op = arr[i].op;
    			int fu = find(u),fv = find(v);
    			if(fu == fv)	//如果二者存在大小关系且又在一个集合，冲突，flag标记为0
    			{ 
    				flag = 0;
    				break;
    			}
    			if(op == '<')
    			{ 
    				es[fv].push_back(fu);	//建边
    				d[fu]++;
    			}
    			if(op == '>')
    			{ 
    				es[fu].push_back(fv);
    				d[fv]++;
    			}
    		}
    	}
    	if(flag == 0)
    	{ 
    		cout << "inconsistent" << endl;
    		return 0;
    	}
    	
    	topsort();
    	if(sum == cnt)		//判断拓扑序的数量和祖先数量是否相同
    		cout << "consistent" << endl;
    	else			//不同说明存在冲突
    		cout << "inconsistent" << endl;
    	
    	return 0;
    }

[B_Chess Tournament]: https://open.kattis.com/problems/chesstournament
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/48897a71347943c5b9ac65ef2765f5bc.png
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/106377870
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/106251880