755C - PolandBall and Forest

2019-11-06 08:29:30

字体：大中小

来源：转载

供稿：网友

题意

有n个结点，分布在数量未知的树上，也就是说这些树可能是一个森林。现在给出每个点在各自树上的最远点，如果有多个最远点的话，那就给出id编号最小的那一个点。

思路1

直接无脑并查集

#include<iostream>using namespace std;int parent[100005];int find(int x) { return x==parent[x]?x:find(parent[x]);}void Union(int a,int b) { int x=find(parent[a]); int y=find(parent[b]); if(x!=y) parent[x]=y; }int main(){ int n; while(cin>>n) { int a,sum=0; for(int i=1;i<=n;i++) parent[i]=i; for(int i=1;i<=n;i++) { cin>>a; Union(i,a); } for(int i=1;i<=n;i++) if(parent[i]==i) sum++; cout<<sum<<endl; } return 0;}

思路2

我猜测思路2才是题者想要的解法？

对于每一个结点，如果它的最远点的最远点是自己本身，则这两个点是树上的两端结点最小的直径，也可以认为是某个树的标示。

记录这样的直径的个数就是树的个数。

# -*- coding: utf-8 -*-# @Author: HaonanWu# @Date: 2017-03-02 10:14:55# @Last Modified by: HaonanWu# @Last Modified time: 2017-03-02 10:45:15n = int(input())p = [0]+list(map(int,input().split()))d = set()for i in range(1,n+1): if p[p[i]] == i: d.add(min(i,p[i]))PRint(len(d))

上一篇：word中排版注意事项

下一篇：SuperMap iDesktop常见问题解答集锦（十）