AO656 2021-03-20 10:12 采纳率: 76.9%
浏览 37
已采纳

这道c++题怎么做啊

有一张n个点m条边的有向无环图(点从1到n编号)和一个初始为空的集合S,每次可以在有向图中取一个同时符合下列两个条件的点x加入集合S:
    1、x不在集合S中。
    2、对任意已经在S中的点y,原图中都应存在一条从x到y或从y到x的路径。
    当集合S为空的时候,你可以选择任何一个点添加。
    你的任务就是,在上述构造s的规则下,求出S最多能够包含多少个点。

 

 

输入输出格式

输入格式:

第一行一个正整数T,表示数据组数。
每组数据第一行有两个正整数n,m,表示该图的点数与边数。
接下来m行,每行两个正整数u,v,其中u<v,表示有一条点u到点v的有向边。

 

 

输出格式:

对每组数据输出一行一个正整数表示答案。

输入输出样例

输入样例#1: 复制

2
4 4
1 2
2 4
1 3
3 4
4 4
1 3
1 4
2 3
2 4

输出样例#1:

3
2

补充说明

在第一组数据中:可以依次添加点1、点4,点3或点2;第二组数据中,可以依次添加点1、点3。 对于30%的数据,n≤15 对于60%的数据,n≤1000 对于100%的数据,1≤T≤10 ; 1≤n≤10000 ;1≤m≤30000,输入中每行两个数 u,v 都满足 u

时间限制:1s 空间限制:256M

  • 写回答

2条回答 默认 最新

  • 小亮点科技 2021-03-20 14:30
    关注

    提供一些思路,你可以先偿试做一下做了以后有问题可以再问。

    1.第一个点取的不同,最终点的数据会不一样。假设第一个点取编号为1的点,得到最张的S为S1,第一个点取编号为2的点,得到最张的S为S2,......第一个点取编号为n的点,得到最张的S为Sn,那么S1到SN中的最大值,即为答案。

    2.计算S1到SN

    每个点的计算方法都一样,我们假设取第i个点,现在求Si

    第一步:将第i个点放在S的第一个位置。

    第二步:从所由路径中找到存在i点的路径(i,x)或(x,i),路径中另一点x如果不在S中则把x入到x中

    这一步就找出了所有跟i的直接路径点。

    第三步:循环第二步找出的所有点,再重复第二步的操作,即找到这些点的直接路径点。把他们放入S中(已经存在的不必放入)。

    第四步,再把第三步中找到的所有新点再重复作第二步和第三步操作,第三步的循环找不到任何新点为止。

    这个时候就得到了Si

    3.求出S1-SN的最大值

     

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常