部落(pta)(并查集) Java以及C++

简介: 部落(pta)(并查集) Java以及C++

题目描述:

在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。

输入格式:

输入在第一行给出一个正整数N(≤10

4

),是已知小圈子的个数。随后N行,每行按下列格式给出一个小圈子里的人:

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数,P[i](i=1,⋯,K)是小圈子里每个人的编号。这里所有人的编号从1开始连续编号,最大编号不会超过10

4

之后一行给出一个非负整数Q(≤10

4

),是查询次数。随后Q行,每行给出一对被查询的人的编号。

输出格式:

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询,如果他们属于同一个部落,则在一行中输出Y,否则输出N。

输入样例:

4

3 10 1 2

2 3 4

4 1 5 7 8

3 9 6 4

2

10 5

3 7

输出样例:

10 2

Y

N

解题思路:

利用并查集,用set集合存放数据

代码:

java(超时)

package text2;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class 部落 {
  static int p[] = new int[10005];
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    for(int i=0;i<10005;i++)
      p[i] = i;
    Set<Integer> numberS = new HashSet<Integer>();
    Set<Integer> numberP = new HashSet<Integer>();
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    for(int i=0;i<n;i++) {
      int p = scanner.nextInt();
      int f = scanner.nextInt();
      numberS.add(f);
      for(int j=1;j<p;j++) {
        int t = scanner.nextInt();
        numberS.add(t);//加入总人数的集合
        Union(f, t);//合并
      }
    }
    System.out.print(numberS.size()+" ");
    for(Integer s:numberS) {
      numberP.add(Find(s));
    }
    System.out.println(numberP.size());
    int m = scanner.nextInt();
    for(int i=0;i<m;i++) {
      int a = scanner.nextInt();
      int b = scanner.nextInt();
      if(Find(a)==Find(b))
        System.out.println("Y");
          else
            System.out.println("N");  
    }
  }
  //找祖先
  public static int Find(int a) {
    if(p[a]!=a) {
      return Find(p[a]);
    }
    return p[a];
  }
//合并两个点的祖先
  public static void Union(int a,int b) {
    a = Find(a);
    b = Find(b);
    if(a!=b) {
      p[a]=b;
    }
  }
}

C++(AC):

#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
int par[10005];

void init(){
    for(int i=0;i<10000;i++){
        par[i]=i;
    }
}

int findEle(int a){        //找到祖先
    if(a!=par[a]){
        return par[a]=findEle(par[a]);
    }
    return par[a];
}

void unionEle(int a,int b){   //合并两个点
    a=findEle(a);
    b=findEle(b);
    if(a!=b)
        par[a]=b;
}
int main()
{
    int n,q;
    cin>>n;
    init();
    set<int>st;
    set<int>stt;
    for(int i=0;i<n ;i++){
        int k;
        cin>>k;
        int a[10005];
        cin>>a[0];
        st.insert(a[0]);
        for(int j=1;j<k;j++){
            cin>>a[j];
            st.insert(a[j]);
            unionEle(a[0],a[j]);
        }
    }
    cout<<st.size()<<" ";
    for(auto it=st.begin();it!=st.end();it++){
        stt.insert(findEle(*it));
    }
    cout<<stt.size()<<endl;
    cin>>q;
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        if(findEle(a)==findEle(b))
            cout<<"Y"<<endl;
        else
            cout<<"N"<<endl;   
    }
    system("pause");
    return 0;
}

相关文章
|
14天前
|
Java Android开发 C++
Java和C++
Java和C++
31 15
WK
|
1月前
|
安全 Java 编译器
C++和Java哪个更好用
C++和Java各具优势,选择取决于项目需求、开发者偏好及目标平台特性。C++性能出色,适合游戏、实时系统等;Java平台独立性强,适合跨平台、安全敏感应用。C++提供硬件访问和灵活编程范式,Java有自动内存管理和丰富库支持。两者各有千秋,需根据具体需求选择。
WK
29 1
|
2月前
|
IDE Java 程序员
C++ 程序员的 Java 指南
一个 C++ 程序员自己总结的 Java 学习中应该注意的点。
24 5
WK
|
1月前
|
开发框架 移动开发 Java
C++和Java哪个更适合开发移动应用
本文对比了C++和Java在移动应用开发中的优劣,从市场需求、学习难度、开发效率、跨平台性和应用领域等方面进行了详细分析。Java在Android开发中占据优势,而C++则适合对性能要求较高的场景。选择应根据具体需求和个人偏好综合考虑。
WK
54 0
WK
|
1月前
|
安全 Java 编译器
C++和Java哪个更适合开发web网站
在Web开发领域,C++和Java各具优势。C++以其高性能、低级控制和跨平台性著称,适用于需要高吞吐量和低延迟的场景,如实时交易系统和在线游戏服务器。Java则凭借其跨平台性、丰富的生态系统和强大的安全性,广泛应用于企业级Web开发,如企业管理系统和电子商务平台。选择时需根据项目需求和技术储备综合考虑。
WK
82 0
|
2月前
|
缓存 并行计算 Java
C++矢量运算与java矢量运算
本文探讨了C++和Java中的矢量运算与标量运算的性能比较,解释了矢量运算的原理和为什么它比标量运算快,包括并行性、数据局部性、指令优化和数据重用等优势。文章还提供了C++和Java的矢量运算示例代码,并展示了运行结果,以证明矢量运算在处理大量数据时的性能优势。
25 0
C++矢量运算与java矢量运算
|
3月前
|
Java Android开发 C++
🚀Android NDK开发实战!Java与C++混合编程,打造极致性能体验!📊
在Android应用开发中,追求卓越性能是不变的主题。本文介绍如何利用Android NDK(Native Development Kit)结合Java与C++进行混合编程,提升应用性能。从环境搭建到JNI接口设计,再到实战示例,全面展示NDK的优势与应用技巧,助你打造高性能应用。通过具体案例,如计算斐波那契数列,详细讲解Java与C++的协作流程,帮助开发者掌握NDK开发精髓,实现高效计算与硬件交互。
164 1
|
4月前
|
Rust 安全 Java
Java代码规范--排版,命名.:Rust能否撼动C++的王座?
系统编程是计算机科学的核心,C++长期占据主导地位,但其内存安全问题备受诟病。Rust以安全性为核心,通过所有权和生命周期概念避免了野指针和内存泄漏。此外,Rust的并发模型和日益丰富的生态系统使其成为现代系统编程的新选择,尤其在安全性和并发性方面表现出色。尽管C++依然强大,但Rust为开发者提供了更安全、易管理的选项,未来有望推动更多系统级应用的发展。
28 0
|
5月前
|
Java Android开发 C++
🚀Android NDK开发实战!Java与C++混合编程,打造极致性能体验!📊
【7月更文挑战第28天】在 Android 开发中, NDK 让 Java 与 C++ 混合编程成为可能, 从而提升应用性能。**为何选 NDK?** C++ 在执行效率与内存管理上优于 Java, 特别适合高性能需求场景。**环境搭建** 需 Android Studio 和 NDK, 工具如 CMake。**JNI** 构建 Java-C++ 交互, 通过声明 `native` 方法并在 C++ 中实现。**实战** 示例: 使用 C++ 计算斐波那契数列以提高效率。**总结** 混合编程增强性能, 但增加复杂性, 使用前需谨慎评估。
149 4
|
4月前
|
算法 Java Linux
Intellij Java JNI 调用 C++
Intellij Java JNI 调用 C++
42 0