寒假集训第一天---并查集题解

codeforces - 209c trails and glades

传送门

题目大意：n个点，m条边。从一号点出发，需要遍历所有有边相连的所有点最后要到一号点。(1 ≤ n ≤ 10⁶; 0 ≤ m ≤ 10⁶)

解法：跑出连通块个数和每个连通块所包含的度数为奇数的点，对于包含2个以上奇度顶点的连通块，先两两相连到只剩两个奇度顶点，然后所有连通块由奇度顶点出发连到另外一个块的奇度顶点，如果一个连通块没有奇度顶点，那就从任意一个偶度顶点出发，从同一偶度顶点回归。统计连通块用并查集

卡点：给的边可能没有连接1号顶点，需要从1号顶点出发和别的连通块相连，边数+1，但是如果一条边都没有，那结果就是0，因为没有其他点了.（看cf样例特判写过.....）

代