1021. Deepest Root (25)——DFS+并查集

时间:2022-02-09 02:05:46

http://pat.zju.edu.cn/contests/pat-a-practise/1021

无环连通图也可以视为一棵树,选定图中任意一点作为根,如果这时候整个树的深度最大,则称其为 deepest root。 给定一个图,按升序输出所有 deepest root。如果给定的图有多个连通分量,则输出连通分量的数量。

1.使用并查集判断图是否为连通的。

2.任意选取一点,做 dfs 搜索,选取其中一个最远距离的点 A,再做一次 dfs,找到的所有距离最远的点以及点 A 都是 deepest root。

考虑到为稀疏图,则使用动态链表

#include<stdio.h>
#include<stack>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std; vector<int> map[];
int f[];
int find(int k){
if(f[k]==-)return k;
else
return f[k]=find(f[k]);
} int um(int a,int b){
int fa,fb;
fa=find(a);
fb=find(b); if(fa==fb)return ;//表示有环 if(fa!=fb)
f[fa]=fb;
return ;
} int step[]; void dfs(int x,int STEP){ int i;
for(i=;i<map[x].size();i++){
if(step[map[x][i]]!=)continue;
step[map[x][i]]=STEP;
dfs(map[x][i],STEP+);
}
} int main()
{
int n;
while(scanf("%d",&n)!=EOF){
int i,a,b; for(i=;i<=n;i++){
f[i]=-;
step[i]=;
} int huan=;
for(i=;i<n;i++){
scanf("%d%d",&a,&b);
if(um(a,b)==)huan=; map[a].push_back(b);
map[b].push_back(a);
}
int connectAdd=;
set<int>set1;
int ttemp;
for(i=;i<=n;i++){
ttemp=find(i);
set1.insert(ttemp);
} if(set1.size()>=||huan==){
printf("Error: %d components\n",set1.size());continue;
}
step[]=;
dfs(,); int max=,ri;
for(i=;i<=n;i++){
if(max<step[i]){
max=step[i];
ri=i;
}
} for(i=;i<=n;i++){
step[i]=;
}
step[ri]=;
dfs(ri,); max=;
for(i=;i<=n;i++){
if(max<step[i]){
max=step[i];
}
} for(i=;i<=n;i++){
if(step[i]==max||step[i]==){
printf("%d\n",i);
}
}
} return ;
}

其实上面的算法还有点问题,虽然AC了

考虑

5
1 2
1 3
2 4
2 5

应该是输出

3

4

5

算法改进 以(第2次dfs最深的点)为起点,再做DFS得到的最深的点,这些点才是所有最深的点

#include<stdio.h>
#include<stack>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std; vector<int> map[];
int f[];
int find(int k){
if(f[k]==-)return k;
else
return f[k]=find(f[k]);
} int um(int a,int b){
int fa,fb;
fa=find(a);
fb=find(b); if(fa==fb)return ;//表示有环 if(fa!=fb)
f[fa]=fb;
return ;
} int step[];
int deepF[];//第2次dfs最深的点
int deepR[];//以(第2次dfs最深的点)为起点,做DFS得到的最深的点 void dfs(int x,int STEP){ int i;
for(i=;i<map[x].size();i++){
if(step[map[x][i]]!=)continue;
step[map[x][i]]=STEP;
dfs(map[x][i],STEP+);
}
} int main()
{
int n;
while(scanf("%d",&n)!=EOF){
int i,a,b,j; for(i=;i<=n;i++){
f[i]=-;
step[i]=;
deepF[i]=;
deepR[i]=;
} int huan=;
for(i=;i<n;i++){
scanf("%d%d",&a,&b);
if(um(a,b)==)huan=; map[a].push_back(b);
map[b].push_back(a);
}
int connectAdd=;
set<int>set1;
int ttemp;
for(i=;i<=n;i++){
ttemp=find(i);
set1.insert(ttemp);
} if(set1.size()>=||huan==){
printf("Error: %d components\n",set1.size());continue;
}
step[]=;
dfs(,); int max=,ri;
for(i=;i<=n;i++){
if(max<step[i]){
max=step[i];
ri=i;
}
} for(i=;i<=n;i++){
step[i]=;
}
step[ri]=;
dfs(ri,); max=;
for(i=;i<=n;i++){
if(max<step[i]){
max=step[i];
}
} for(i=;i<=n;i++){
if(step[i]==max||step[i]==){
//printf("%d\n",i);
deepF[i]=;
deepR[i]=;
}
} for(i=;i<=n;i++){
if(deepF[i]==)continue;
for(j=;j<=n;j++)step[j]=; dfs(i,);
for(j=;j<=n;j++){
if(step[j]==max)deepR[j]=;
}
} for(i=;i<=n;i++){
if(deepR[i]==)printf("%d\n",i);
}
} return ;
}

1021. Deepest Root (25)——DFS+并查集的更多相关文章

  1. PAT甲题题解-1021&period; Deepest Root &lpar;25&rpar;-dfs&plus;并查集

    dfs求最大层数并查集求连通个数 #include <iostream> #include <cstdio> #include <algorithm> #inclu ...

  2. PAT-1021 Deepest Root &lpar;25 分&rpar; 并查集判断成环和联通&plus;求树的深度

    A graph which is connected and acyclic can be considered a tree. The height of the tree depends on t ...

  3. &lbrack;PAT&rsqb; 1021 Deepest Root &lpar;25&rpar;(25 分)

    1021 Deepest Root (25)(25 分)A graph which is connected and acyclic can be considered a tree. The hei ...

  4. PAT 甲级 1021 Deepest Root &lpar;25 分&rpar;(bfs求树高&comma;又可能存在part数part&gt&semi;2的情况)

    1021 Deepest Root (25 分)   A graph which is connected and acyclic can be considered a tree. The heig ...

  5. 1021&period; Deepest Root &lpar;25&rpar; -并查集判树 -BFS求深度

    题目如下: A graph which is connected and acyclic can be considered a tree. The height of the tree depend ...

  6. 1021&period; Deepest Root &lpar;25&rpar;

    A graph which is connected and acyclic can be considered a tree. The height of the tree depends on t ...

  7. PAT &lpar;Advanced Level&rpar; 1021&period; Deepest Root &lpar;25&rpar;

    先并查集判断连通性,然后暴力每个点作为根节点判即可. #include<iostream> #include<cstring> #include<cmath> #i ...

  8. 1021 Deepest Root &lpar;25&rpar;(25 point&lpar;s&rpar;)

    problem A graph which is connected and acyclic can be considered a tree. The height of the tree depe ...

  9. 1021 Deepest Root &lpar;25 分&rpar;

    A graph which is connected and acyclic can be considered a tree. The height of the tree depends on t ...

随机推荐

  1. Mac下github项目检出与提交

    项目检出 如果你的git还没有代码仓库,可以用过git的代码仓库页面新建一个你的仓库 创建git上的仓库后,我们还需要建立本地的仓库,所以打开Mac终端,建立本地仓库文件夹(这里我用HelloC),然 ...

  2. 工作中常用shell之ssh登陆不用输入&quot&semi;yes&quot&semi;

    ip="192.168.5.166"ssh $ip -o StrictHostKeyChecking=no           //ssh登陆不用输入"yes" ...

  3. 1&period;单件模式&lpar;Singleton Pattern&rpar;

    意图:为了保证一个类仅有一个实例,并提供一个访问它的全局访问点. 1.简单实现(多线程有可能产生多个实例) public class CommonSigleton { /// <summary& ...

  4. 理解sparse coding

    理解sparse coding 稀疏编码系列: (一)----Spatial Pyramid 小结 (二)----图像的稀疏表示——ScSPM和LLC的总结 (三)----理解sparse codin ...

  5. 转&colon;SCHEME 语言是怎么来的 -1

    导言 Scheme 是 LISP 的一个方言(dialect).著名的 SICP 书就是以 Scheme 为教学语言(实际上 SICP 的作者就是 Scheme 的作者). 虽然 Scheme 本身只 ...

  6. JAVA实现DAO基本层CRUD操作

    随着shh2各种操作方便框架.越来越多JAVA WEB效率,可是,假设在不了解这些框架使用的场合的情况下,一拿到项目就盲目地选择这些框架进行系统架构的搭建,就有可能造成非常多不是必需的资源浪费. 在项 ...

  7. SublimeText3插件安装及使用

    之前写过一篇文章讲了安装PackageControl,这里就不做赘述了,需要的朋友移步到这篇文章:Sublime Text安装package control 安装插件方法:通过preferencs-- ...

  8. JS案例四:表格的隔行换色以及高亮显示

    <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title> ...

  9. 利用python实现两个文件夹的同步

    其实无论windows还是Linux,简单地去实现两个两个文件夹的同步只需系统自带的复制命令加参数就可以了. WINDOWS : xcopy 源文件夹\* 目标文件夹 /s /e /y Linux : ...

  10. 《大规模web服务开发技术》笔记

    前段时间趁空把<大规模web服务开发技术>这本书看完了,今天用一下午时间重新翻了一遍,把其中的要点记了下来,权当复习和备忘.由于自己对数据压缩.全文检索等还算比较熟,所以笔记内容主要涉及前 ...