谎言与诚实谜题

诚实村与谎言村

一天，你跟随渔夫出海打鱼，在海上遇到了大风浪而迷失了方向，小船被刮到了一座小岛上。岛上有两个相邻的村子，一个叫诚实村，一个叫谎言村，诚实村的村民只会说真话，从不撒谎，而谎言村的村民则只说谎话，从不说真话。所以你决定想办法区分出这不同的两组人，弄清楚谁说的是真话，这样才能够找到回去的方向。这两个村的村民很热情，有问必答，你要求每位村民给你一份他们认为是说谎者的名单。这些村民世世代代都生活在这里，所以他们非常清楚谁在说谎。但是为了不得罪人，每位村民勉强地只给了你一份不全的名单，当然这些名单也不能尽信。

你必须编写一个程序来筛选你所收集到的这些信息，并判断哪些村民是在说真话，哪些村民是在说谎话。两个村的村民人数很多，所以你的程序必须能快速并有效的处理大量数据。

输入规范

你的程序必须获取一个唯一的命令行参数，即文件的名称。打开文件并且解析里面的数据。这些数据以村民的数量  n 开头，行尾另起一新行。后面跟着是连续的  n 块信息，每块信息描述的是一个村民所举报的那些说谎者名单。每一块的格式如下： 

• <accuser name>  <m>（其中：accuser name 表示举报人名字，m 表示被举报说谎的人数。）

而后紧跟  m 行，每一行包含一个被举报的人员名字。 accuser name 和  m 被一些制表符（tab）和空格隔开。 m 总是在 [0,  n] 区间。所有人员的名字只包含字母且是唯一的并区分大小写。 

输入文件示例：

• 5
  Stephen 1
  Tommaso
  Tommaso 1
  Galileo
  Isaac 1
  Tommaso
  Galileo 1
  Tommaso
  George 2
  Isaac
  Stephen

输出规范

你的程序输出必须由两个数字组成，数字之间由一个空格隔开，结尾另起一新行（换行符为 " \n"），打印至标准输出。第一个数字是说谎者和诚实者中人数较多的一组人数； 第二个数字是人数较少的一组人数。我们保证这些测试数据只有一个正确的解决方法。 

输出示例如下：

• 3 2

====================个人解决方案===========================

/**
 * 因为题目没有要求分清到底谁是真谁是假，只需要计算出对立双方的人数
 * 相互指认的双方必定属于对立的两个阵营，所以说双方只要有碰撞就说明分别属于对立
 * 假定第一个属于真话阵营，那么他所指认的必定是假话阵营的，
 * 相反也成立，如果这个人是假话阵营，那么他所指认的必定是真话阵营的
 * 这样我们可以构建一个这样的表结构
 * A->B,C
 * B->A
 * C->A
 * 通过表可以确认那些人是相互对立的，通过遍历表中的节点来确认具体属于那个阵营
 * 同时将已经确定属于统一阵营的人存储起来，减少遍历的深度和次数来达到优化的目的
 * 有三个辅助的列表：真话列表，假话列表，未决列表
 *
 * 在第一遍对表结构的遍历不足以确定所有人的阵营时，
 * 通过不断增加的真假话列表的含量来对未决列表中人员来确认其阵营
 * （最差情况需要完全来通过未决列表来确定）
 * author cnsworder
 * mail [e-mail]
 * 2010-07-19
 */
#include <string>
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <list>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::ifstream;
using std::list;


//总人数
long userCount = 0;
//假定的真话阵营的人数
long good_count = 0;
//假定的假话阵营的人数
long bad_count = 0;
//真话人名列表，用于遍历对比
list<string> true_users;
//假话人名列表
list<string> false_users;

class user_info {
public:
	string name;
	bool flag;
	list<string> bad_users;
};

#pragma pack(0)

/**
 * 相互对立的人的列表
 */
//class bad_info {
//public:
//	string name;
//	string bad_name;
//};
//list<bad_info> t_bad;
list<user_info> users;
list<user_info> temps;

int isGood(user_info name);
void verify();
bool foreachlist(list<user_info>::iterator b);

/**
 *  假设第一个为真的
 *  统计说真话和假话的人数
 */
void countBad() {
	list<user_info>::iterator m = users.begin();
	good_count++;
	true_users.push_back(m->name);
	for (list<string>::iterator b = m->bad_users.begin(); b
			!= m->bad_users.end(); b++) {
		false_users.push_back(*b);
	}
	

	m++;
	for (; m != users.end(); m++) {
		int flag = true;
		flag = isGood(*m);
		//可以检查数据是否在列表中重复，减少后期遍历压力
		if (flag > 0) {
			good_count++;
			true_users.push_back(m->name);
			for (list<string>::iterator b = m->bad_users.begin(); b
					!= m->bad_users.end(); b++) {
				false_users.push_back(*b);
			}
		} else if (flag < 0) {
			bad_count++;
			false_users.push_back(m->name);
			for (list<string>::iterator b = m->bad_users.begin(); b
					!= m->bad_users.end(); b++) {
				true_users.push_back(*b);
			}
		}
	}
    while(!temps.empty())
	    verify();

}
/**
 * 验证这个人是否已经确认说真话还是假话，否则，加入到未决队列中，在后期验证
 * 根据返回值确定这个人属于那种类型>0真话，<0假话， =0未决
 */
int isGood(user_info user) {

	for (list<string>::iterator g = true_users.begin(); g != true_users.end(); g++) {
		if (user.name.compare(*g) == 0) {
			return 1;
		}
	}
	for (list<string>::iterator g = false_users.begin(); g != false_users.end(); g++) {
		if (user.name.compare(*g) == 0) {
			return -1;
		}
	}
	temps.push_back(user);
	return 0;
}
/**
 * 当系统积累一些数据后来辨识那些未决数据的状况，通过递归来实现
 * 如果队列为空则停止递归，最差情况可能会陷入递归的死循环，
 * 但是根据题意所有的数据是可以确认的，
 * 并且随着积累知识数据的增加这种情况出现这种情况会为零
 */
void verify() {

	if(temps.size() < 1) {
		return;
	}
	for (list<user_info>::iterator b = temps.begin(); b != temps.end(); b++) {
			//list特性删除数据后需要重新构建iterator，所以改用递归来抵消带来的影响
			if(foreachlist(b)) {
				verify();
				return;
			}
	}
}
/**
 * 遍历知识列表，确认则将增加对应计数器，并从未决列表中删除，并返回true，否则返回false
 * 因为从列表中删除list的iterator指针会自动增加1，通过返回来确认继续遍历还是递归，直接通过判断自增可以优化掉
 */
bool foreachlist(list<user_info>::iterator b) {
	for (list<string>::iterator g = b->bad_users.begin();
			g != b->bad_users.end(); g++) {
	for (list<string>::iterator t = true_users.begin();
			t != true_users.end(); t++) {
		if (t->compare(*g) == 0) {
			temps.erase(b);
			good_count ++;
			return true;
		}
	}	for (list<string>::iterator t = false_users.begin();
			t != false_users.end(); t++) {
		if (t->compare(*g) == 0) {
			temps.erase(b);
			bad_count ++;
			return true;
		}
	}
	}
	return false;
}

void readFile(char* fileName) {
	ifstream filestream(fileName);

	filestream >> userCount;

	for (int m = 0; m < userCount; m++) {
		string name;
		int i;
		filestream >> name >> i;
		user_info user;
		user.name = name;
		user.flag = true;
		for (int n = 0; n < i; n++) {
			string badName;
			filestream >> badName;
			user.bad_users.push_back(badName);
		}
		users.push_back(user);
	}
}

int main(int argc, char **argv) {
//	if (argc != 2) {
//		cout << "error:no much arg!!" << endl;
//		return 1;
//	}

	readFile(argv[argc - 1 ]);
	countBad();
	if (good_count < bad_count) {
		long t = good_count;
		good_count = bad_count;
		bad_count = t;

	}
	cout << good_count << " " << bad_count << endl;

	return 0;
}

这个算法不完善，时间有限，并且STL库在有些系统上在递归时产生段错误。如果将队列改为不能重复的在大数据量时会更好。大家帮忙看看有没有更好的方案。

•