[CF1385E] Directing Edges - 拓扑排序

2021-03-03 19:29

阅读：615

标签：cto fine i++ out cti main == script namespace

## [CF1385E] Directing Edges - 拓扑排序

### Description

给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中没有环，如果可以做到请输出该图，否则直接输出 NO

### Solution

只添加有向边，进行拓扑排序，令所有无向边也从拓扑序小的节点指向拓扑序大的节点，就一定不会成环

``` cpp
#include 
using namespace std;

#define int long long

const int N = 1000005;
vector g[N];

int ind, topo[N];

void dfs(int p)
{
    if (topo[p])
        return;
    topo[p] = -1;
    for (int q : g[p])
        dfs(q);
    topo[p] = --ind;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i > und;
    for (int i = 1; i > t >> x >> y;
        if (t)
            g[x].push_back(y);
        else
            und.push_back({x, y});
    }
    for (int i = 1; i  topo[j])
            {
                cout > t;
    while (t--)
    {
        solve();
    }
}

标签：cto fine i++ out cti main == script namespace

原文地址：https://www.cnblogs.com/mollnn/p/14384058.html

上一篇：Java程序设置为开机自启动

下一篇：树莓派图形编程（Python，C++，Scratch，BlockPi）Part.1 RGB灯间隔亮

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[CF1385E] Directing Edges - 拓扑排序
文章链接：http://soscw.com/index.php/essay/59658.html

亲，登录后才可以留言！

[CF1385E] Directing Edges - 拓扑排序

评论

热门文章

推荐文章

最新文章

置顶文章