Liar, Liar
As a newbie on a particular internet discussion board, you notice a distinct trend among its veteran members; everyone seems to be
either unfailingly honest or compulsively deceptive. You decide to try to identify the members of the two groups, starting with the assumption that every senior member either never lies or never tells the truth. You compile as much data as possible, asking
each person for a list of which people are liars. Since the people you are asking have been around on the board for a long time, you may assume that they have perfect knowledge of who is trustworthy and who is not. Each person will respond with a list of people
that they accuse of being liars. Everyone on the board can see that you are a tremendous n00b, so they will grudgingly give you only partial lists of who the liars are. Of course these lists are not to be taken at face value because of all the lying going
on.
You must write a program to determine, given all the information you‘ve collected from the discussion board members, which members
have the same attitude toward telling the truth. It‘s a pretty popular discussion board, so your program will need to be able to process a large amount of data quickly and efficiently.
Input Specifications
Your program must take a single command line argument; the name of a file. It must then open the file and read out the input data.
The data begins with the number of veteran members n followed by a newline. It continues with n chunks of information, each defining the accusations made by a single member. Each chunk is formatted as follows:
<accuser name> <m>
followed by m lines each containing the name of one member that the accuser says is a liar. accuser name and m are separated by some
number of tabs and spaces. m will always be in [0, n]. All member names contain only alphabetic characters and are unique and case-sensitive.
Example input file:
5
Stephen 1
Tommaso
Tommaso 1
Galileo
Isaac 1
Tommaso
Galileo 1
Tommaso
George 2
Isaac
Stephen
Output Specifications
Your output must consist of two numbers separated by a single space and followed by a newline, printed to standard out. The first
number is the size of the larger group between the liars and the non-liars. The second number is the size of the smaller group. You are guaranteed that exactly one correct solution exists for all test data.
Example output:
3 2
--------------------------------------------------------------------------------
Merge-FInd Set, Similar to the previous blogs.
#include <stdio.h>
#include <string>
#include <iostream>
#include <map>
#include <string.h>
#include <vector>
using namespace std;
map<string, int> personNO;
vector<int> f;
int find(int x) {
return x == f[x] ? x : (f[x] = find(f[x]));
}
int main() {
freopen("in.txt","r",stdin);
int N, M, i, j, cnt = 0, x, y, cntX, cntY;
string name1, name2;
scanf("%d",&N);
for (i = 0; i < N*2; ++i)
f.push_back(i);
for (i = 0; i < N; ++i) {
cin>>name1;
if (personNO.find(name1) == personNO.end()) {
personNO.insert(make_pair(name1, cnt++));
}
scanf("%d", &M);
for (j = 0; j < M; ++j) {
cin>>name2;
if (personNO.find(name2) == personNO.end()) {
personNO.insert(make_pair(name2, cnt++));
}
f[personNO[name1]] = find(personNO[name2] + N);
f[personNO[name2]] = find(personNO[name1] + N);
}
}
x = find(0), cntX = 1, cntY = 0;
for (i = 1; i < N; ++i)
if (find(i) == x) {
++cntX;
}
else {
y = find(i);
++cntY;
}
if (cntX > cntY)
printf("%d %d", cntX, cntY);
else
printf("%d %d", cntY, cntX);
return 0;
}
CareerCup Liars Merge-Find Set,布布扣,bubuko.com
CareerCup Liars Merge-Find Set
原文：http://blog.csdn.net/taoqick/article/details/20567251
