食物链确实是道不错的并查集的题，与以往的应用不同的是，这个是带权的，而带的权就是权两边端点的关系，这个关系要满足传递性。而划分集合的依据是，集合中的点可以确定这个关系。对于常用的并查集的应用的话，这个关系指的就是属于了。而这道题就是不断的维护一个保持这样关系的数据结构集合，如果当前要添加进来的某个关系与集合中的结构发生冲突，就是假话了。难点在于合并时的关系维护（这个简单，直接修改合并过来集合的根节点的关系就可以），其次是路径压缩的时候，对于这个操作，在回朔的时候，当之前的父节点操作完，说明父节点已经接到这个集合的根节点下，这个父节点的关系也已经确定了，对于当前节点，先不压缩过去，先根据父节点的关系和当前节点与该节点的关系，推出当前节点的关系后，再压缩过去，这样就完成了，路径压缩时候的关系更新。
感谢：
http://wxdlut.blog.163.com/blog/static/128770158200982754311269/http://www.chenyajun.com/2010/02/28/4507http://www.joansky.com/87.html
代码 #include < iostream > #include < string > #include < vector > #include < queue > #include < math.h > using namespace std; const int MAX = 50005 ; int N, K; struct NODE{ int f, w; NODE() { f = - 1 ; w = 0 ; } NODE( int ff, int ww) : f(ff), w(ww) {}}node[MAX]; void ready(){ for ( int i = 1 ; i <= N; i ++ ) node[i] = NODE();} int myFind( int x){ if (node[x].f == - 1 ) return x; int f = myFind(node[x].f); node[x].w += node[node[x].f].w; node[x].w %= 3 ; node[x].f = f; return f;} void join( int x, int y, int z){ int xx = myFind(x); int yy = myFind(y); node[yy].f = xx; node[yy].w = ( - node[y].w - z + node[x].w + 9 ) % 3 ;} int main(){ while (scanf( " %d%d " , & N, & K) != 2 ) { scanf( " %d%d " , & N, & K); int ans = 0 ; ready(); while (K -- ) { int a, b, c; scanf( " %d%d%d " , & c, & a, & b); if (a > N || b > N) { ans ++ ; continue ; } int aa = myFind(a); int bb = myFind(b); if (aa == bb) { if (c == 1 && node[a].w != node[b].w) ans ++ ; else if (c == 2 ) { if ((node[a].w - node[b].w + 6 ) % 3 != 1 ) ans ++ ; } } else join(a, b, c - 1 ); } printf( " %d\n " , ans); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/08/06/1793887.html
