放在全局变量）"/>
More is better （并查集）（大容量数组要放在全局变量）
DescriptionMr Wang wants some boys to help him with a project. Mr王 想让boys 帮他一个项目 Because the project is rather complex, the more boys come, the better it will be. Of course there are certain requirements. 来的boys越多越好。也有要求 选了一个足够大的房子 来装他们 The boy （who are not been chosen） has to leave the room immediately. 没被选的boy 立马离开房间 There are 10000000 boys( in the room )(numbered from 1 to 10000000 )(at the very beginning). 一开始 房间里有10000000个boy，每个人编号从1-10000000 (After Mr Wang's selection) any two( of them )(who are still in this room )should be friends (direct or indirect), or there is only one boy left. 在王的选择之后，任意两个boy 应该成为朋友（ 直接或者间接）， 或者 只有一个剩下了 Given all the direct friend-pairs, you should decide the best way. 给你所有的直接 朋友对，你应该决定最好的办法。 InputThe first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤ 10000000) 第一行：直接朋友对n
OutputThe output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep. 输出：最大值of boys （王能keep的） Sample InputSample OutputHint
A and B are friends(direct or indirect), B and C are friends(direct or indirect), then A and C are also friends(indirect). In the first sample {1,2,5,6} is the result. In the second sample {1,2},{3,4},{5,6},{7,8} are four kinds of answers. |
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <stack>
#include <iomanip>
using namespace std;// 类内部 申请 10000000的int 数组，运行不了
// 类内部 改成 vector 能运行，但是time不行
// 干脆别用类了，直接在全局变量里面申请！int father[10000001]; // 0 ~ 10000000 记录上级/老大
int contain[10000001]; // 包含多少小弟
int minIndex; // 范围
int maxIndex; // 范围
int cnt; //连通分量的个数void initialize(int minIndex, int maxIndex) {// 1 ~ 4minIndex = minIndex;maxIndex = maxIndex;cnt = maxIndex - minIndex + 1; // 连通分量的个数for (int i = minIndex; i <= maxIndex ; i++) {father[i] = -1;contain[i] = 1;}
}int getRoot(int x) {if (father[x] == -1) {return x; // 自己就是老大} else {//自己不是老大，自己有上级// 上级是set老大 还是 图上的父节点？int d = father[x];int root = getRoot(d);if (d != root) {father[x] = root; // 直接跟root算了，不跟图上的父节点contain[d] -= contain[x]; // contain少了，投奔root了}return root;}}bool isConnected(int x, int y) {return getRoot(x) == getRoot(y);
}bool connect(int x, int y) {int xRoot = getRoot(x);int yRoot = getRoot(y);if (xRoot == yRoot) {//cout << "已经在同一个set里面了" << endl;return false; // 已经在同一个set里面了，已经在同一个连通分量里面了} else {if(contain[x] >= contain[y]) {// x 人多势大， y投奔xfather[yRoot] = xRoot;contain[xRoot] += contain[yRoot];} else {// y人多势大，x投奔yfather[xRoot] = yRoot;contain[yRoot] += contain[xRoot];}}cnt --; //连通分量少1
}int getCnt() {return cnt;
}
int getContain(int x) {return contain[x];
}void show(int minIndex, int maxIndex) {cout << "---目前情况---" << endl;cout << "father :";for (int i = minIndex; i <= maxIndex; i++) {cout << setw(4) << father[i] << "\t";}cout << endl;cout << "index :";for (int i = minIndex; i <= maxIndex; i++) {cout << setw(4) << i << "\t";}cout << endl << endl;cout << "contain :";for (int i = minIndex; i <= maxIndex; i++) {cout << setw(4) << contain[i] << "\t";}cout << endl;cout << "index :";for (int i = minIndex; i <= maxIndex; i++) {cout << setw(4) << i << "\t";}cout << endl;cout << "---打印完毕---" << endl << endl;
}int main() {int n;// 直接朋友对 的数目int x, y;while(cin >> n) {initialize(1, 10000000);for (int i = 1; i <= n ; i++) {cin >> x >> y;connect(x, y);}int maxContain = 1;for (int i = 0; i <= 10000000; i++) {if (getContain(i) > maxContain) {maxContain = getContain(i);}}// show(1, 6);cout << maxContain << endl;;}
}不要自作聪明，原来是写了 vector<int> record;把指定的人全加入vector 然后再查询谁contain的最多，结果是超时。
或许是stl本身有点慢吧？不如数组方便.
更多推荐
More is better （并查集）（大容量数组要放在全局变量）
发布评论