P2078 朋友

    • 730通过
    • 2.2K提交
  • 题目提供者 大神cyd
  • 评测方式 云端评测
  • 标签 并查集 递归
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    小明在A公司工作,小红在B公司工作。

    题目描述

    这两个公司的员工有一个特点:一个公司的员工都是同性。

    A公司有N名员工,其中有P对朋友关系。B公司有M名员工,其中有Q对朋友关系。朋友的朋友一定还是朋友。

    每对朋友关系用两个整数(Xi,Yi)组成,表示朋友的编号分别为Xi,Yi。男人的编号是正数,女人的编号是负数。小明的编号是1,小红的编号是-1.

    大家都知道,小明和小红是朋友,那么,请你写一个程序求出两公司之间,通过小明和小红认识的人最多一共能配成多少对情侣。(包括他们自己)

    输入输出格式

    输入格式:

    第1行,4个空格隔开的正整数N,M,P,Q。

    之后P行,每行两个正整数Xi,Yi。

    之后Q行,每行两个负整数Xi,Yi。

    输出格式:

    一行,一个正整数,表示通过小明和小红认识的人最多一共能配成多少对情侣。(包括他们自己)

    输入输出样例

    输入样例#1: 复制
    4 3 4 2
    1 1
    1 2
    2 3
    1 3
    -1 -2
    -3 -3
    
    输出样例#1: 复制
    2

    说明

    对于30%数据,N,M<=100,P,Q<=200

    对于80%数据,N,M<=4000,P,Q<=10000.

    对于全部数据,N,M<=10000,P,Q<=20000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。