http://poj.org/problem?id=2942
思路:首先考虑建边,但是会发现直接建边很难处理。
那么考虑通过能相邻的图去建立边.建完边后结合题意,题目说要求一些骑士永远不可能去开会。开会的要求有一个>=3的奇环。
所以题目问的是哪些骑士是不在任何一个奇环里的。
所以考虑把补图上所有的缩点后的点联通分量里面判一下奇环。
奇环的判定也就是染色法判定是不是二分图。
这个题大概调了5小时。
做了之后发现点连通分量的板子是不一样的,因为割点是属于多个连通分量里面的,不能直接按照求强连通分量的缩点那样直接弹出栈。
另外注意在主函数里面把每个dcc[]打上对应的编号,然后在判奇数环的时候注意在补图上判奇数环,dcc[]里面是没有连边关系的。同时注意遍历点的时候是要在同一个dcc[]里的
提供一组数据:
7 12
1 7
2 1
3 6
7 6
1 4
4 7
4 2
1 5
2 3
2 7
6 5
5 3
0 0
ans:7
http://poj.org/bbs?problem_id=2942(更多的见discuss)