[Hnoi2010]Planar
Time Limit:10000MS Memory Limit:65536K
Total Submit:118 Accepted:33
Case Time Limit:1000MS
Description
Input
Output
Sample Input
Sample Output
Source
Day1
恩。。这个题目还是挺水的。。就是我好久没写判二分图了多次WA囧。。。
把这个哈密顿回路拉成一个环。。那么可以发现如果两条边在环上相交。。
显然需要一个在环内一个在环外。。就可以看成2-染色。。
然后就没有然后了。。
平面图判定可以在线性时间内完成
回复中国脑筋：Orz神牛！！！这个算法太神牛了我完全不会只好写这样的傻叉算法囧啊。。请原谅我的无知囧。。。
数据太弱。100组m=10000的数据直接爆裸判。
爆判都可以过，那是没好好做，真的亏死了。好像这个用欧拉定理还可以优化到N^2的吧。