UVa 657

The die is cast

from Volume 2. Data Structures :: Graphs

Description

一道模式识别题。输入一张像素图，图上有几个骰子。要求识别图上的骰子的点数。并且从小到大排序输出。但是要注意：

• 两点之间，上下左右相邻的才算靠在一起，如果是斜角相邻则算分开的两个点。

Solution

求一张无向图的连通分支数，可以得知有几个骰子。然后把骰子作为一张子图再求其连通分支数，就可以知道骰子上的点数。可以用 DFS 来求连通分支数，则二重的 DFS 即可 AC 。