题目如下：
提示：输入很大，你忍一下，小心超时
AC代码如下：
#include#include #include #include using namespace std; const int N = 2009*2; int bcj[N]; int find(int x) { if (bcj[x] < 0) return x; return bcj[x] = find(bcj[x]); } void join(int x, int y) { x = find(x); y = find(y); if (x == y) return; bcj[x] += bcj[y]; bcj[y] = x; } int num(int x) { x = find(x); return -bcj[x]; } int main() { int t; scanf("%d",&t); int cnt = 0; while(t--) { int flag = 1; int n,m; scanf("%d %d",&n,&m); for(int i = 1;i<=N;i++) bcj[i] = -1; cnt++; while(m--) { int x,y; scanf("%d %d",&x,&y); join(x,y+n); join(y,x+n); if((find(x)==find(x+n))||(find(y)==find(y+n))) flag = 0; } printf("Scenario #%d:n",cnt); if(flag) printf("No suspicious bugs found!nn"); else printf("Suspicious bugs found!nn"); } }
代码解析：
join(x,y+n); join(y,x+n); if((find(x)==find(x+n))||(find(y)==find(y+n))) flag = 0;
每次合并完 都判断一下
如果：
x 与 x+n || y 与 y+n
有相同的祖宗就让 flag = 0
最后勉励自己一下：
欲穷千里目，更上一层楼。 —— 王之涣《登鹳雀楼》
