网站建设费属于业务宣传费吗,如何建立和设置公司网站,宁晋县建设局网站,中国建设集团门户网站题意#xff1a;
在这个城市里有两个黑帮团伙#xff0c;现在给出N个人#xff0c;问任意两个人他们是否在同一个团伙 1.输入D x y代表x于y不在一个团伙里 2.输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里
题目#xff1a;
The police office in Tadu…题意
在这个城市里有两个黑帮团伙现在给出N个人问任意两个人他们是否在同一个团伙 1.输入D x y代表x于y不在一个团伙里 2.输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里
题目
The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)
Assume N (N 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M 10^5) messages in sequence, which are in the following two kinds: D [a] [b] where [a] and [b] are the numbers of two criminals, and they belong to different gangs. A [a] [b] where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.
Input
The first line of the input contains a single integer T (1 T 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.
Output
For each message “A [a] [b]” in each case, your program should give the judgment based on the information got before. The answers might be one of “In the same gang.”, “In different gangs.” and “Not sure yet.”
Sample Input
1 5 5 A 1 2 D 1 2 A 1 2 D 2 4 A 1 4
Sample Output
Not sure yet. In different gangs. In the same gang.
Sponsor
分析
这道题用的是种类并查集并查集把给出的人分成几个集合每个集合之间的人的关系不确定对同一个集合保存和本人不为同一队的人本着敌人的敌人便是朋友的原则用并查集同一集合为同一队不同集合为不同队。说的我自己都绕晕了23333 1.首先特殊解很重要当N2时他们属于不同的帮派因为题目有说两个帮派至少有一个人。 2. 1只要输入D就将a,b两个合并归在同一集合并将改他们的关系。 2输入A的时候判断a,b是否合并过如果两个不属于同一个集合的话就不能确定他们是否在同一个帮派。 3若合并过即前面已经出现过则有确定关系即是否在同一帮派。此时只要判定其dp【】值是否相同即为一个队为同一帮派否则不在。 原因我在把一个集合合并到另一个集合时把x根节点的dp变成和y根节点dp相对的每次连儿子保证和父亲不是一个帮派同时更新父亲然后在查找的时候要修改dp值注意回溯因为生成的树每一层和隔层的dp值是相对的0和1因为dp的值只能为0和1只有两个帮派所以类别偏移用位运算 4若我太啰嗦可参照 如下AC代码有步骤详解
#include stdio.h
#define M 100010
int dp[M],f[M];
int i,n,m,a,b;
int t;
int find(int x)
{int num;if(f[x]!x){numfind(f[x]);dp[x]dp[x]^dp[f[x]];//类别偏移可以用按位异或运算当两对应的二进位相异时结果为1。dp值是相对的0和1return f[x]num;}return x;
}
void dfs(int x,int y)
{int ufind(x);int vfind(y);f[u]v;///dp[u]~(dp[y]^dp[x]);//类别偏移用按位取反运算即dp值是相对的0和1dp[u]1^dp[y]^dp[x]; /**更新x的父节点跟yy的父节点的关系,效果与按位取反相同.每次连儿子保证和父亲不是一个帮派同时更新父亲然后find时候注意回溯一下。*/
}
int main()
{scanf(%d,t);while(t--){scanf(%d%d,n,m);for(i0; in; i){dp[i]0;//0表示同派f[i]i;}for(i1; im; i){char s[5];scanf(%s%d%d,s,a,b);if(s[0]D)//只要输入D就将a,b两个合并并将改他们的关系dfs(a,b);else//,输入A的时候判断a,b是否合并过没有输出无法确定合并过再判断是不是同一派。{if(n2) //特殊解printf(In different gangs.\n);else if(find(a)find(b))///前面已经出现过则有确定关系即是否在同一帮派{if(dp[a]dp[b])printf(In the same gang.\n);elseprintf(In different gangs.\n);}elseprintf(Not sure yet.\n);}}}return 0;
}
