codeforces-1385E(拓扑排序)

2021-04-13 15:27

阅读：679

标签：ret int lang pos 生成 lse bit har 排序

Directing Edges

题目描述：

给定n个点m条边，其中一些边是有向的，一些边是无向的，现在你需要将这些无向的边确定方向，并判断是否可以生成一个有向无环图

思路：

显而易见如果给出的有向边没有形成环的话，剩下的无向边一定可以使他们不形成环，于是只需要将给定的有向边做一遍拓扑排序，判断是否已经成环，未成环的话就将所有无向边按拓扑序定向即可使图无环

代码：

#include
using namespace std;
using ll = long long;
const ll N = 1e6;
const double PI = acos(-1.0);
#define Test ll tesnum;tesnum = read();while(tesnum--)
ll read();
vector g[200005];
vector> v;
int deg[N],pos[N];
int cnt;
int main()
{
    Test{
        cnt = 0;
        v.clear();
        int n,m;
        cin>>n>>m;
        for(int i = 1; i >w>>x>>y;
            v.emplace_back(make_pair(x,y));
            if(w==1){
                g[x].emplace_back(y);
                deg[y]++;
            }
        }
        queue q;
        for(int i = 1; i pos[x.second]){
                    cout

codeforces-1385E(拓扑排序)

标签：ret int lang pos 生成 lse bit har 排序

原文地址：https://www.cnblogs.com/cloudplankroader/p/13341693.html

上一篇：springcloud02- Eureka 服务注册与发现

下一篇：Python多线程

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：codeforces-1385E(拓扑排序)
文章链接：http://soscw.com/index.php/essay/75248.html

亲，登录后才可以留言！

codeforces-1385E(拓扑排序)

Directing Edges

题目描述：

思路：

代码：

评论

热门文章

推荐文章

最新文章

置顶文章