个人中心
文章发布
退出
作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
24
4
<分区>
如果我有一个有向图。如何检查此图的所有节点对 (u,v) 是否相关？
关系表示[u,v]或[v,u]之间存在联系。
举个例子:
在此图像中，最左边的图具有所有对之间的关系。右一不是；
为了解决这个问题，我尝试了从原始给定图及其反转图开始的 BFS。当且仅当所有节点都被两个 bfs 访问时，我们才有一个相关图。否则图表不相关。
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
void DFS(bool *vst,vii &G,int ini){
queue<int> q;
q.push(ini);
int cur;
while(!q.empty()){
cur = q.front();
q.pop();
if(vst[cur])
continue;
vst[cur] = true;
vi &adj = G[cur];
for (vi::iterator it = adj.begin(); it != adj.end(); ++it)
q.push(*it);
}
}
int main(void){
//N is the number of Nodes and M is the number of Edges
int n,m;
scanf("%d %d",&n,&m);
vii G(n+1); //graph
vii R(n+1);//reversed graph
//read and fill both graphs
for (int i = 0,u,v; i < m; ++i) {
scanf("%d %d",&u,&v);
G[u].push_back(v);
R[v].push_back(u);
}
//get some node with outdegree and indegree > 0
int S = -1;
for (int i = 1; i <= n; ++i){
if(G[i].size() > 0 && R[i].size() > 0){
S = i;
break;
}
}
bool vst1[n+1];
bool vst2[n+1];
for (int i = 1; i <= n; ++i)
vst1[i] = vst2[i] = false;
if(S != -1){
DFS(vst1, G, S);
DFS(vst2, R, S);
}
int i;
for (i = 1; i <= n; ++i){
if((vst1[i] || vst2[i]) == false){
i = -1;
break;
}
}
if(i == n+1)
puts("All pairs related");
else
puts("All pairs not-related");
}
但是这个解决方案在 30% 的测试用例中是错误的；这是一个竞赛问题，我无权访问输入 =(
我做错了什么？
输入描述:
The first line has two integers N and M (1 ≤ N,M ≤ 100000) and the next M lines has two integers U and V (1 ≤ U,V ≤ N).
Sample Input 1
3 3
1 3
2 3
3 1Sample Input 2
3 2
1 3
2 3Sample Output 1
All pairs relatedSample Output 2
All pairs not-related
24
4
0
我想显示阿拉伯文字，但字符 المملك 显示。 例如，在 المملكة العربية السعودية 上显示单词 المملك٩ ا
我的应用程序正在 java + MSSQL 和 MySQL 上运行。下面的查询适用于 MSSQL，但不适用于 MySql。在 mysql 中，当我编写如下查询时，它给出了错误的结果 查询 select
根据 is_destructible 的定义( http://eel.is/c++draft/meta.unary.prop#lib:is_destructible ), is_destructib
我有一个数据库表，其中有一列我对波斯字母进行了分类，以便稍后使用 MySQL WHERE 选择。一切都适用于所有字母，但我在选择在数据库中存储为 (Ù†) 的字母 (?) 和存储为 (Ú†) 的 (?
我知道像这样的可选链接: someOptional?.someProperty 基本上是 someOptional.map { $0.someProperty } 但是，我发现同时做这两件事是不可能的
u-boot配置文件中的以下配置我看不懂 CONFIG_SYS_EXTRA_OPTIONS="SYS_SDRAM_SIZE=0x20000000" 好像在 u-boot 代码中设置 DRAM 大小。但
我对以下两个方法声明感到困惑: private T funWorks(T child, U parent) { // No compilation errors }
给定如下 API: class Bar { ... } class Foo extends Bar { ... } 在 Java 的 Optional 类型中，我们可以说: Optional fooO
我有一个文件，每行有两个字符: $ cat roman Ⅱ Ⅲ nut 当我用 sort -u 对这个文件进行排序时，只显示一行: $ sort -u roman Ⅱ Ⅱ是代码点U+2161，Ⅲ是代码
我正在尝试将 C 数组分配给 C++ std::array。 我该如何做到这一点，最干净的方式并且不制作不需要的拷贝等？ 什么时候做 int X[8]; std::array Y = X; 我得到一个
我有以下案例类: case class [Q Length[T] 但是，我收到一条错误消息，说 需要三个参数，而我只给出了两个。我希望它像这样工作: type Area[T] = [Length[T
它是 well documented那个[T; n]可以强制到[T] .下面的代码也是well-formed : fn test(){ let _a: &[i32] = &[1, 2, 3];
我正在尝试使用 tweepy 在 Tkinter 窗口上显示我的 Twitter 时间线。这是代码 import tweepy import tkinter consumer_key = 'xxxxx
我正在使用以下包含 letter ü 的文本片段: test für fur test 代码如下: import re for m in re.finditer(r, line, re.IGNOREC
我对 USQL 很陌生，想知道如何在 select 语句中将“日期时间”转换为“日期”。另外，我如何摆脱毫秒和上午/下午？我真的很感激这方面的任何帮助。谢谢你们。 最佳答案 下面是有效的代码。注意括号
在 U-SQL 自定义代码(代码隐藏或程序集)中可以调用外部服务，例如bing搜索或 map 。 谢谢， 纳西尔 最佳答案 由于以下原因，目前不支持此功能: 想象一下，您编写了一个 UDF 或 UDO
我想 ping 出多个以太网端口。 u-boot 仅支持单个以太网端口是否存在固有限制？ 最佳答案 Can u-boot support more than one ethernet port? 是的
我最近开始学习Prolog，但无法解决如何将三个列表合并的问题。 我能够合并两个列表: %element element(X,[X|_]). element(X,[_|Y]):-
我们使用 Beaglebone 黑色定制板。我编辑了一个链接器脚本文件以添加内存部分以在其中记录一些信息: . = ALIGN(4); .logging : { _log_begin
我们使用 Beaglebone 黑色定制板。我编辑了一个链接器脚本文件以添加内存部分以在其中记录一些信息: . = ALIGN(4); .logging : { _log_begin
我是一名优秀的程序员,十分优秀！