L2-031 深入虎穴

题目大意

主要思路

使用并查集维护到根节点距离

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;const int N = 100010;
int n, p[N], d[N];
int st[N];int find(int x)
{if(x != p[x]){int t = find(p[x]);d[x] += d[p[x]];p[x] = t;}return p[x];
}int main(void)
{scanf("%d", &n);for(int i = 1; i <= n; i++) p[i] = i;for(int i = 1; i <= n; i++){int k, t, a;t = find(i);scanf("%d", &k);while(k--){scanf("%d", &a);st[a] = 1;int pa = find(a);if(t != pa)//维护到根节点距离{p[pa] = t;d[pa] = d[i] + 1;}}}int r;//求起点for(int i = 1; i <= n; i++){if(!st[i]){  r = i;break;}}int res = -1, ans;for(int i = 1; i <= n; i++){if(find(i) == r && d[i] > res){res = d[i];ans = i;}}cout << ans << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！