C++ 程序：战争中的城市连通性报警系统

#include\x20 #include\x20 #include\x20 using\x20namespace\x20std;

//\x20并查集 class\x20UnionFind\x20{ private: \x20\x20vector\x20parent; public: \x20\x20UnionFind(int\x20n)\x20{ \x20\x20\x20\x20parent.resize(n); \x20\x20\x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20<\x20n;\x20i++)\x20{ \x20\x20\x20\x20\x20\x20parent[i]\x20=\x20i; \x20\x20\x20\x20} \x20\x20}

\x20\x20int\x20find(int\x20x)\x20{ \x20\x20\x20\x20if\x20(parent[x]\x20!=\x20x)\x20{ \x20\x20\x20\x20\x20\x20parent[x]\x20=\x20find(parent[x]); \x20\x20\x20\x20} \x20\x20\x20\x20return\x20parent[x]; \x20\x20}

\x20\x20void\x20unite(int\x20x,\x20int\x20y)\x20{ \x20\x20\x20\x20int\x20root_x\x20=\x20find(x); \x20\x20\x20\x20int\x20root_y\x20=\x20find(y); \x20\x20\x20\x20if\x20(root_x\x20!=\x20root_y)\x20{ \x20\x20\x20\x20\x20\x20parent[root_x]\x20=\x20root_y; \x20\x20\x20\x20} \x20\x20} };

int\x20main()\x20{ \x20\x20int\x20N,\x20M; \x20\x20cin\x20>>\x20N\x20>>\x20M;

\x20\x20//\x20初始化并查集 \x20\x20UnionFind\x20uf(N);

\x20\x20//\x20存储通路信息 \x20\x20vector<pair<int,\x20int>>\x20roads(M); \x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20<\x20M;\x20i++)\x20{ \x20\x20\x20\x20cin\x20>>\x20roads[i].first\x20>>\x20roads[i].second; \x20\x20\x20\x20//\x20合并连通的城市 \x20\x20\x20\x20uf.unite(roads[i].first,\x20roads[i].second); \x20\x20}

\x20\x20int\x20K; \x20\x20cin\x20>>\x20K; \x20\x20vector\x20lostCities(K); \x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20<\x20K;\x20i++)\x20{ \x20\x20\x20\x20cin\x20>>\x20lostCities[i]; \x20\x20}

\x20\x20bool\x20isGameOver\x20=\x20true; \x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20<\x20K;\x20i++)\x20{ \x20\x20\x20\x20if\x20(i\x20>\x200)\x20{ \x20\x20\x20\x20\x20\x20cout\x20<<\x20endl; \x20\x20\x20\x20} \x20\x20\x20\x20if\x20(uf.find(lostCities[i])\x20!=\x20lostCities[i])\x20{ \x20\x20\x20\x20\x20\x20cout\x20<<\x20"City\x20"\x20<<\x20lostCities[i]\x20<<\x20"\x20is\x20lost."; \x20\x20\x20\x20}else\x20{ \x20\x20\x20\x20\x20\x20cout\x20<<\x20"Red\x20Alert:\x20City\x20"\x20<<\x20lostCities[i]\x20<<\x20"\x20is\x20lost!"; \x20\x20\x20\x20\x20\x20isGameOver\x20=\x20false; \x20\x20\x20\x20} \x20\x20}

\x20\x20if\x20(isGameOver)\x20{ \x20\x20\x20\x20cout\x20<<\x20endl\x20<<\x20"Game\x20Over."; \x20\x20}

\x20\x20return\x200;