hdu 3172 Virtual Friends (字符串的并查集)

一开始一直wa,因为第一个数字t也是多组输入。

然后一直超时,因为我用的是C++里面的cin,所以非常耗时,几乎比scanf慢了10倍,但是加上了一个语句后:

std::ios::sync_with_stdio(false);                //是用来禁用cin这个兼容性的特性,禁用后就相差无几了

 #include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
map<string, string>fa;
map<string, int>Rank;
const int maxn = ;
string a[maxn];
string b[maxn]; string Find(string x){
if (x == fa[x])
return x;
else
return fa[x] = Find(fa[x]);
} void set_union(string x, string y){
string xx = Find(x);
string yy = Find(y);
//cout << "fa: " << xx << " " << yy << endl;
if (xx == yy){
cout << Rank[xx] << endl;
}
else{
fa[yy] = xx;
Rank[xx] += Rank[yy];
cout << Rank[xx] << endl;
}
/*
if (Rank[xx] > Rank[yy]){
fa[yy] = xx;
Rank[xx] += Rank[yy];
cout << Rank[xx] << endl;
}
else if (Rank[xx]==Rank[yy]){
fa[yy] = xx;
Rank[xx]+=Rank[yy];
cout << Rank[xx] << endl;
}
else{
fa[yy] = xx;
Rank[yy] += Rank[xx];
cout << Rank[yy] << endl;
}
*/
} void init(int sum){
for (int i = ; i < sum; i++){
fa[a[i]] = a[i];
fa[b[i]] = b[i];
Rank[a[i]] = Rank[b[i]] = ;
}
} int main(){
std::ios::sync_with_stdio(false);
int t;
while (cin>>t){
while (t--){
int n;
cin >> n;
for (int i = ; i < n; i++){
cin >> a[i];
cin >> b[i];
}
init(n);
for (int i = ; i < n; i++){
//cout << "#" << i << endl;
//cout << a[i] << " " << b[i] << endl;
set_union(a[i], b[i]);
}
}
}
//system("pause");
return ;
}
上一篇:将github上的项目源码导入到eclipse中


下一篇:C# List 排序