UnionFind
class UnionFind {
struct Node {
explicit Node(int root = 0) : root(root), dist(0) {}
int root;
int dist;
};
public:
explicit UnionFind(int size, int ringSize) : nodeVec(size), ringSize(ringSize) {
for (int x = 0; x < size; ++x) {
nodeVec[x].root = x;
}
}
inline bool isConnected(int x, int y) { return findRoot(x) == findRoot(y); }
inline bool isSame(int x, int y) { return !((nodeVec[x].dist - nodeVec[y].dist) % ringSize); }
inline bool isEat(int x, int y) { return !((nodeVec[x].dist - nodeVec[y].dist - 1) % ringSize); }
bool sameUnion(int x, int y) {
const int xRoot = findRoot(x);
const int yRoot = findRoot(y);
if (xRoot != yRoot) {
nodeVec[xRoot].root = yRoot;
nodeVec[xRoot].dist = nodeVec[y].dist - nodeVec[x].dist;
return true;
}
return false;
}
bool eatUnion(int x, int y) {
const int xRoot = findRoot(x);
const int yRoot = findRoot(y);
if (xRoot != yRoot) {
nodeVec[xRoot].root = yRoot;
nodeVec[xRoot].dist = nodeVec[y].dist - nodeVec[x].dist + 1;
return true;
}
return false;
}
private:
int findRoot(int x) {
vector<int> distVec;
distVec.reserve(16);
int root = x;
while (nodeVec[root].root != root) {
root = nodeVec[root].root;
distVec.push_back(nodeVec[root].dist);
}
for (int i = static_cast<int>(distVec.size()) - 2; i >= 0; --i) {
distVec[i] += distVec[i + 1];
}
for (int i = 0; nodeVec[x].root != root; ++i) {
nodeVec[x].dist += distVec[i];
const int y = nodeVec[x].root;
nodeVec[x].root = root;
x = y;
}
return root;
}
vector<Node> nodeVec;
int ringSize;
};
main
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int n, k, d, x, y;
scanf("%d%d", &n, &k);
UnionFind unionFind(n + 1, 3);
int res = 0;
for (int i = 0; i < k; ++i) {
scanf("%d%d%d", &d, &x, &y);
if (x < 1 || x > n || y < 1 || y > n) {
++res;
continue;
}
if (d == 1) {
if (unionFind.isConnected(x, y)) {
if (!unionFind.isSame(x, y)) {
++res;
}
} else {
unionFind.sameUnion(x, y);
}
} else if (d == 2) {
if (unionFind.isConnected(x, y)) {
if (!unionFind.isEat(x, y)) {
++res;
}
} else {
unionFind.eatUnion(x, y);
}
}
}
printf("%d\n", res);
return 0;
}
哥们你们公司C++编成规范是google的么?
以前的公司不是google规范。新入职的公司是在google规范基础上,进行了一小点修改和增加。这周末,我修改这段代码的风格。