Regionals 1997 >> North America - North Central NA
问题链接：。
问题简述：若干组用例，最后两个-1（-1 -1）结束。每个测试用例包括若干组边（两个整数组成），最后两个0（0 0）结束。判定每个测试用例是否为一棵树。
问题分析：判定有向图是否为一棵树的问题。可以用那些边构造一个并查集，构建并查集时，如果有向边的两个结点的根相同则不是一棵树，同时所有的结点指向的根应该是相同的。
注意点：结点虽然用整数表示，然而是随意的，而且范围不定。
程序说明：程序中，假定最大的结点不超过100000。将所有结点放入集合中，判定结点的根是否相同时，只需要考虑集合中的元素。
参考链接：。
AC的程序如下（HDU1325未AC，其他三个都AC，错误信息是ACCESS_VIOLATION，有点不明白）：
/* UVALive5461 UVA615 POJ1308 HDU1325 Is It A Tree? */#include#include #include using namespace std;const int MAXN = 100000;// 并查集类class UF {private: vector v;public: UF(int n) { for(int i=0; i<=n; i++) v.push_back(i); } int Find(int x) { for(;;) { if(v[x] != x) x = v[x]; else return x; } } bool Union(int x, int y) { x = Find(x); y = Find(y); if(x == y) return false; else { v[x] = y; return true; } }};int main(){ int src, dest, casecount=0, root; bool ans; for(;;) { UF uf(MAXN); set is; ans = true; while(cin >> src >> dest) { if(src == -1 && dest == -1) return 0; if(src == 0 && dest == 0) { if(ans) { root = -1; for(set ::iterator iter=is.begin(); iter!=is.end(); iter++) { if(root == -1) root = uf.Find(*iter); else if(uf.Find(*iter) != root) { ans = false; break; } } } cout << "Case " << ++casecount << (ans ? " is a tree." : " is not a tree.") << endl; break; } else if(ans) { if(uf.Union(src, dest)) { is.insert(src); is.insert(dest); } else ans = false; } } } return 0;}
改进后AC的程序如下（HDU1325出现Time Limit Exceeded，可能与集合类set有关，其他三个都AC）：
/* UVALive5461 UVA615 POJ1308 HDU1325 Is It A Tree? */#include#include #include #include using namespace std;const int MAXN = 100000;// 并查集int v[MAXN+1];class UF {private: int length;public: UF(int n) { length = n; for(int i=0; i<=n; i++) v[i] = i; } // 压缩 int Find(int x) { if(x == v[x]) return x; else return v[x] = Find(v[x]); } bool Union(int x, int y) { x = Find(x); y = Find(y); if(x == y) return false; else { v[x] = y; return true; } } void reset() { for(int i=0; i<=length; i++) v[i] = i; }};int main(){ int src, dest, casecount=0, root; bool ans; UF uf(MAXN); set is; for(;;) { ans = true;// while(cin >> src >> dest) { while(scanf("%d%d", &src, &dest) != EOF) { if(src == -1 && dest == -1) return 0; if(src == 0 && dest == 0) { if(ans) { root = -1; for(set ::iterator iter=is.begin(); iter!=is.end(); iter++) { if(root == -1) root = uf.Find(*iter); else if(uf.Find(*iter) != root) { ans = false; break; } } }// cout << "Case " << ++casecount << (ans ? " is a tree." : " is not a tree.") << endl; if(ans) printf("Case %d is a tree.\n", ++casecount); else printf("Case %d is not a tree.\n", ++casecount); break; } else if(ans) { if(uf.Union(src, dest)) { is.insert(src); is.insert(dest); } else ans = false; } } is.clear(); uf.reset(); } return 0;}