本文共 1404 字，大约阅读时间需要 4 分钟。

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 <= n; i++)g[i].clear();        for(int i = 1; i <= n; i++)deg[i] = pos[i] = 0;        for(int i = 1; i <= m; i++){            int w,x,y;            cin>>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 <= n; i++){            if(deg[i]==0)                q.push(i);        }        while(!q.empty())        {            int u = q.front();            q.pop();            pos[u] = ++cnt;            for(int i = 0; i < g[u].size(); i++){                deg[g[u][i]]--;                if(deg[g[u][i]]==0){                    q.push(g[u][i]);                }            }        }        if(cnt==n){            cout<<"YES"<
        
         pos[x.second]){ cout<
         
          <<" "<
          
           <
          
         
        
       
      
     
    
   

转载地址：https://www.cnblogs.com/cloudplankroader/p/13341693.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！