现在的位置: 首页 > 综合 > 正文

hdu3560Graph’s Cycle Component 并查集

2013年08月26日 ⁄ 综合 ⁄ 共 418字 ⁄ 字号 评论关闭

看了那么多题解  看不懂怎么判断环就算了 尴尬代码还是错的- -

哎……

一个大牛写的 ,很简单的思路

http://yimaoblog.diandian.com/post/2011-02-22/18444418#notes

 

 

思想:并查集判断部分的个数,用点的度来判断是否是环,点构成环的充要条件是该环中每个点的度皆为2;

       代码流程:1、初始化每个点的度为0,每个点所属集合(根节点)为其自身,标记值flag=1;

                         2、对于每组输入数据,相应的点的度加1;查找两个点的根节点,如果不相等则合并之;

                         3、遍历每个点,如果其度不为2,找到其根节点,将其根节点标记flag=0,表示该集合不可能为环;

                         4、遍历查找答案,看f[i]与i是否相等,若相等,则部分数加1,再判断其标记值是否为1,若是则环数加1;

 

抱歉!评论已关闭.