无向图中边的定向
even degrees
题目链接:https://atcoder.jp/contests/agc035/tasks/agc035_b
题意:给出一张无向简单连通图,判断以下命题是否存在并给出一种方案,使得每个点的出度均为偶数.其中$n,m\in(1,1e5)$
分析:直接给无向边定向看起来不好下手,先从简单的情况考虑
对于一条链,每个点的度数为1或2,那么让两端点的出度为0,中间的任意,就可以得到答案.
扩展到树上.叶子结点的度数一定为1,那么所有的叶边一定由父亲出发指向叶子.考虑处理两个树上度数为奇的非叶结点,手玩容易发现,将树链反转,仅影响两端点度数的奇偶性,对其他的没有影响.如果有偶数个出度为奇的结点,一定可以通过若干次反转使整棵树满足条件;反之,如果只有奇数个出度为奇的结点,那么一定没有合法方案.
再看一张连通图上,可以先跑出一颗生成树.对于非树边任意定向,不会影响答案,奇数点的奇偶性不会改变.然后再按树的思路反转父边,最后一定满足要求.
综合一下可以推出,如果边数为奇,一定无解;反之亦然.