个人中心
gpt4 book ai didi

c++ - 给定一个 DI-Graph。检查所有节点对是否存在来自 (u,v) 或 (v,u) 的路径

转载 作者：太空狗 更新时间：2023-10-29 21:39:45 24 4
gpt4 key购买 nike

<分区>

如果我有一个有向图。如何检查此图的所有节点对 (u,v) 是否相关？
关系表示[u,v]或[v,u]之间存在联系。

举个例子:
在此图像中，最左边的图具有所有对之间的关​​系。右一不是；

Example

为了解决这个问题，我尝试了从原始给定图及其反转图开始的 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 1

Sample Input 2
3 2
1 3
2 3

Sample Output 1
All pairs related

Sample Output 2
All pairs not-related

24 4 0
文章推荐： c# - 配置为使用 Markdown 时，Orchard 中的语法高亮代码片段
文章推荐： c# - Clipboard.Clear() 使 Outlook 和 Visual Studio 崩溃
文章推荐： c# - WCF - 我什么时候应该使用 netTcpBinding
文章推荐： c# - 从 Controller 操作中手动捆绑和缩小 JS
太空狗
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com