bzoj 1370: [Baltic2003]Gang团伙 并查集

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1370


把一个点拆成两个点,i–>i,i+n

如果两个人是朋友,合并(x,y)

如果是敌人,合并(x,y+n)  (y,x+n)

如果一个连通块有一个点在1~n内,那么它会使ans++

所以最后数一下1~n(注意不是到n*2)里有多少个不同的连通块

 

发表评论