HomeWork1

---恢复内容开始---

HomeWork1

a)项目描述
最近公共祖先问题。对于100%的数据，满足N<=10^5，M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），所有询问中出现过的名字均在之前所描述的N对父子关系中出现过，第一个出现的名字所确定的人是其他所有人的公共祖先。

b) 错误描述
项目完成后，对于输入的样例数据无论如何都得不出正确的结果。再确认思路无误后，进行了大量的错误排查，仍无法定位错误所在地。由于数据量巨大，当时没有现成的输入数据，无法通过常规的方式进行debug，当时只能仔细思考，推导代码的走势。

c) 错误解决
由于该项目是用来解决大数据量的问题，在数据结构方面进行了大量的优化，其中最明显的地方就是对于数入数据的重排。利用vector来存大量的输入数据，数据和数据下标组成一个数据元，当时在数据遍历时并没有将数据元作为一个基本单位，而是将数据作为基本单位，导致遍历时访问了错误的数据，最终导致了错误的结果。修正后上传至系统，得出了正确的结果。

d)源代码

#include <iostream>
#include <vector>
#include <map>
#include <memory.h>

using namespace std;

int far[100010],represent[100010],true_num,int_far,int_son,int_name1,int_name2,state[100010];
map <string, int> name_str_int;
string name_int_str[100010];
vector<int> son[100010],left_next[100010];
int input[100010];

int GetNum(string);
int dfs(int);
int Represent(int);

int main()
{
cin.sync_with_stdio(0);
cin.tie(0);

int N,M;
string Father_i,Son_i,Name1_i,Name2_i;

name_str_int.clear();
true_num=0;
memset(state,0,sizeof(state));
for(int i=1; i<100010; i++)
represent[i]=i;

cin>>N;
while(N--)
{
cin>>Father_i>>Son_i;
int_far=GetNum(Father_i);
int_son=GetNum(Son_i);
son[int_far].push_back(int_son);
far[int_son]=int_far;
}

cin>>M;
for(int i=1; i<=M; i++)
{
cin>>Name1_i>>Name2_i;
int_name1=name_str_int.at(Name1_i);
int_name2=name_str_int.at(Name2_i);
if(int_name1==int_name2)
input[i]=int_name1;
else
{
left_next[int_name1].push_back(int_name2);
left_next[int_name1].push_back(i);
}
}
dfs(1);
for(int i=1; i<=M; i++)
cout<<name_int_str[input[i]]<<endl;

}

int Represent(int number)
{
while(number!=represent[number])
number=represent[number];
return number;
}

int dfs(int cur_node)
{
//cout<<"-->"<<name_int_str[cur_node];
state[cur_node]=1;

for(int i=0; i<left_next[cur_node].size(); i=i+2)
{
if(state[left_next[cur_node][i]])
{
input[left_next[cur_node][i+1]]=Represent(left_next[cur_node][i]);
}
else
{
left_next[left_next[cur_node][i]].push_back(cur_node);
left_next[left_next[cur_node][i]].push_back(left_next[cur_node][i+1]);
}
}

for(int i=0; i<son[cur_node].size(); i++)
dfs(son[cur_node][i]);

represent[cur_node]=far[cur_node];
//state[cur_node]=2;
}

int GetNum(string name)
{
if(!name_str_int.count(name))
{
name_int_str[++true_num]=name;
name_str_int.insert(pair<string, int> (name, true_num));
return true_num;
}
return name_str_int.at(name);
}