PAT1021Deepset Root
2024-08-24 01:31:59
题意:
连通则输出最深点。第一步找某个点的最深的,然后从这个最深的点查找其他最深点,做并集。
不连通则输出连通图个数。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<set>
#include<vector>
#include<cstring>
#include<iterator>
#include<algorithm>
using namespace std;
#define N (10010) int n;
vector<int> vcMap[N];
bool bVis[N] = {};
int maxLen = ;
set<int> setRes;
set<int> setRes2;
set<int> setRes3;
void dfs(int curI,int iLen)
{
bVis[curI] = ;
++iLen;
if(iLen > maxLen)
{
setRes.clear();
maxLen = iLen;
setRes.insert(curI);
}
else if(iLen == maxLen)
{
setRes.insert(curI);
}
for(int i=;i<vcMap[curI].size();++i)
{
if(!bVis[vcMap[curI][i]])
dfs(vcMap[curI][i],iLen);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<n-;++i)
{
int a,b;
scanf("%d%d",&a,&b);
vcMap[a].push_back(b);
vcMap[b].push_back(a);
}
int k=;
for(int i=;i<=n;++i)
{
if(!bVis[i])
{
++k;
dfs(i,);
set_union(setRes.begin(), setRes.end(), setRes2.begin(),
setRes2.end(), inserter(setRes2, setRes2.begin()));
}
}
if(k==)
{
for(int i=;i<=n;++i)
{
if(setRes2.find(i)!=setRes2.end())
{
memset(bVis,,sizeof(bVis));
dfs(i,);
break;
}
}
set_union(setRes.begin(), setRes.end(), setRes2.begin(),
setRes2.end(), inserter(setRes2, setRes2.begin()));
set<int>::iterator it = setRes2.begin();
for(;it != setRes2.end();it++)
printf("%d\n",*it);
}
else
printf("Error: %d components\n",k);
return ;
}
最新文章
- vs 2015 ";加载该页时出错。"; 解决方案
- 洛谷 P1007 独木桥
- 以forin的方式遍历数组时进行删除操作的注意点
- 两系统用asp.net forms 身份验证方式实现跨域登录信息共享
- 分享自制的13套 JQuery Mobile 界面主题(追加4套新款)
- Electro桌面应用开发之HelloWorld
- linux下(Ubuntu、centos)添加永久静态路由的方法
- leetcode 101 Symmetric Tree ----- java
- bug - colorWithPatternImage:
- jQuery+Ajax+PHP+Mysql实现分页显示数据
- OS-MAC: An Efficient MAC Protocol for Spectrum-Agile Wireless Networks
- IOS开发中如何给UIImageView添加点击事件
- js运算
- Linux学习历程——SUID、SGID、SBIT简介
- 为什么预处理和参数化查询可以防止sql注入呢?
- Mysql监控调优
- PHP设计模式单例模式的继承实现
- window.name实现跨域
- idea创建文件类型失败(xml之类的失效
- [USACO 2018 Jan Gold] Tutorial