codeforces 129 B. Students and Shoelaces

2015年12月5日 0 作者 CrazyKK

http://codeforces.com/contest/129/problem/B
题意:n个点。m条边。每一次会将图中度为1的点加入到等待队列中。然后一起删掉,记为一次操作。当删掉一个点的时候,与它相连的边也全部删掉。问一共做进行多少次操作。使得图中不再有度为1的点。
思路:重点是用开一个数组deg[i]记录点i的度。这样比用.size()高明太多。。因为我们并不需要知道具体删了哪条边。我们只要知道与点i相连的点的边数因为点i被删除而减少了1.