题目名称 | 531. 图的平方 |
---|---|
输入输出 | ljb.in/out |
难度等级 | ★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 10 |
题目来源 | cqw 于2011-03-11加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:35, 提交:190, 通过率:18.42% | ||||
digital-T | 100 | 0.012 s | 15.57 MiB | C++ |
belong.zmx | 100 | 0.025 s | 17.77 MiB | C++ |
zqzas | 100 | 0.025 s | 17.77 MiB | C++ |
Pom | 100 | 0.025 s | 17.77 MiB | C++ |
王者自由 | 100 | 0.025 s | 26.58 MiB | C++ |
王者自由 | 100 | 0.025 s | 26.58 MiB | C++ |
joeyolui | 100 | 0.036 s | 0.54 MiB | Pascal |
李振文 | 100 | 0.040 s | 16.95 MiB | Pascal |
raywzy | 100 | 0.041 s | 30.83 MiB | C++ |
hjr1995 | 100 | 0.043 s | 16.66 MiB | Pascal |
本题关联比赛 | |||
20110311 | |||
20110311 |
关于 图的平方 的近10条评论(全部评论) |
---|
有向图G=(V,E)的平方是图G^2=(V,E^2),该图满足下列条件:(u,w)∈E^2当且仅当对v∈V,有(u, v)∈E,且(v,w)∈E。亦即,如果图G中顶点u和w之间存在着一条恰包含两边的路径时,则G^2必包含该边(u,w)。
请编程序对于给定的有向图G,查询边(u,w)是否存在于平方图G^2中。
第一行有两个整数,v(1<=v<=100000),m(1<=m<=1000),其中v表示图G的顶点个数,(顶点按1~v编号);
接下来有m行,每行包含4个整数u1,u2,v1,v2,表示在图G中,顶点区间[u1,u2]中的每一个顶点至顶点区间[v1,v2]中的每一个顶点都有边相连;
接下来有一行,一个整数n(1<=n<=1000),表示查询的个数;
接下来有n行,每一行有4个整数,x1,x2,y1,y2,表示一个询问,即询问在平方图G^2中,其顶点区间[x1,x2]中的每一个顶点至顶点区间[y1,y2]中的每一个顶点是否都有边。
对于每一个查询,如果结果为“是”则输出"Yes",否则输出"No",如果有多个查询,每个结果单独占一行。
6 2 1 3 5 6 4 5 2 3 1 2 3 4 6
No
注:图G与G^2中的边数均不会超过2000000.