看了那么多题解 看不懂怎么判断环就算了 代码还是错的- -
哎……
一个大牛写的 ,很简单的思路
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;