2016-11-02 14:56发布
用一个bool join［max_n］数组保存点是否已经有边连接，在遍历边时，如果边两端的点x和y的join［x］和join［y］都等于1，则说明这两个点都有边连接他们了，则不考虑这条边。这样可以吗？
两个节点 join 为 1 并不能说明两个点在同一个联通块的。也就是说可能两个点在不同联通块内而都有别边连接，那么这条边会合并两个联通块。所以还是并查集吧。当然有一种叫做 link-cut-tree 的数据结构也可以轻松维护最小生成树，本质也是维护联通块的连通性。
最多设置5个标签!
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://wenda.whatsns.com/data/attach/logo/logo.png', '推荐 egil 的问题《kruscal用数组代替并查集可以吗？》','https://wenda.whatsns.com/q-304572.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
付费偷看金额在0.1-10元之间
两个节点 join 为 1 并不能说明两个点在同一个联通块的。也就是说可能两个点在不同联通块内而都有别边连接，那么这条边会合并两个联通块。所以还是并查集吧。
当然有一种叫做 link-cut-tree 的数据结构也可以轻松维护最小生成树，本质也是维护联通块的连通性。
一周热门 更多>