简答题 偏难
#7238

发现它,抓住它 一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=10…

发现它,抓住它

一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:

D [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为

A [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为

注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。

时间限制:1000

内存限制:65536

输入

第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。

输出

对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.“,如果不是,回答"In different gangs.”,如果不确定,回答”Not sure yet."。

样例输入

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

样例输出

Not sure yet.
In different gangs.
In the same gang.
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; template &lt;class T&gt; struct DisjointSet {   int *parent;   T *data;   map&lt;T, int&gt; m;   int capacity;   int size;   DisjointSet(int max = 1000) {     capacity = max;     size = 0;     parent = new int[max + 1];     data = new T[max + 1];   }   ~DisjointSet() {     delete[] parent;     delete[] data;   }   bool insert(T x) {     if (size == capacity)       return false;     size++;     data[size] = x;     parent[size] = -1;     m[x] = size;     return true;   }   int getIndex(T x) {     for (int i = 1; i &lt;= size; i++)       if (data[i] == x)         return i;     return -1;   }   int find(T x) {     typename map&lt;T, int&gt;::iterator it;     it = m.find(x);     if (it == m.end())       return -1;     int i, rt;     i = rt = it-&gt;second;     while (parent[rt] &gt; 0)       rt = parent[rt];     return rt;   }   void unionSet(T x, T y) {     int rx, ry;     rx = find(x);     ry = find(y);     if (rx == -1 || ry == -1)       return;     if (rx == ry)       return;     if (parent[rx] &lt; parent[ry]) {       parent[rx] += parent[ry];       parent[ry] = rx;     } else {       parent[ry] += parent[rx];       parent[rx] = ry;     }     find(x);     find(y);   } }; int main() {   int t;   cin &gt;&gt; t;   while (t--) {     DisjointSet&lt;int&gt; s;     int n, m;     cin &gt;&gt; n &gt;&gt; m;     for (int i = 1; i &lt;= n; i++)       s.insert(i);     for (int i = 1; i &lt;= m; i++) {       int a, b;       char c;       cin &gt;&gt; c &gt;&gt; a &gt;&gt; b;       if (c == 'D')         s.unionSet(a, b);       else {         if (s.find(a) != s.find(b))           cout &lt;&lt; "Not sure yet.";         else if (s.parent[a] == s.parent[b])           cout &lt;&lt; "In the same gang.";         else           cout &lt;&lt; "In different gangs.";         cout &lt;&lt; endl;       }     }   }   return 0; }</pre>
这道题暂未补解析。