首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#7419

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

发现它,抓住它

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

1. D [a] [b]

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

2. 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><p><br/></p>
这道题暂未补解析。