蓝桥杯每日一题（拓扑排序）

//3696构造有向无环图

有向无环图才有拓扑排序，有环的话不能进行拓扑，因为会导致环中一个结点（环的入口位置）其入度永远无法变成0。

先判断图是否可拓扑序，如果本来就不能就直接No，可以的话。可以按照拓扑序。确定某个边的方向的时候，只要其起点拓扑序小于其终点即可。

要注意认真：YES格式写错了看了半天；

一直报错，但是感觉没错，看不出来了。

#include<bits/stdc++.h>
using namespace std;
//3696构造有向无环图
const int N=2e5+10;
//拉链法存图
int idx=0;
int e[N],h[N],ne[N];//存图
int d[N];//存入度
vector<pair<int,int>>a;
int p[N];//存拓扑序；
void add(int x,int y)
{
    //先保存当前边的终点
    //头插法将其插入到h[a]所在的拉链。
    //h[a]指向新插入的节点
    //idx++更新
   e[idx]=y;
   ne[idx]=h[x];
   h[x]=idx++;
}

int tuopu(int n)
{
    int cnt=0;
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(!d[i])
        {q.push(i);
        p[i]=cnt++;
        }
    }
    while(!q.empty())
    {
        auto t=q.front();//拿出队头结点
        q.pop();
        for(int i=h[t];i!=-1; i=ne[i])//找所有出边指向点的idx
        {
            d[e[i]]--;
            if(d[e[i]]==0)
            {
                p[e[i]]=cnt++;
                q.push(e[i]);
            }

        }
    }
    return cnt;
}


int main()
{
   int T,n,m,t;
   cin>>T;
   while(T--)
   {
   memset(h,-1,sizeof(h));
   memset(d,0,sizeof(d));
      cin>>n>>m;
      while(m--)
      {
          int x,y;
          cin>>t>>x>>y;
          if(t)add(x,y),d[y]++;
          a.push_back({x,y});

      }
      if(a.size()!=n&&tuopu(n)!=n)cout<<"NO"<<endl;
      else
       {
           cout<<"YES"<<endl;
           //如何比较两个点的拓扑序
           for(auto t:a)
           {
               int q=t.first;
               int z=t.second;
               if(p[q]<=p[z])cout<<q<<" "<<z<<endl;
               else cout<<z<<" "<<q<<endl;
           }
       }
       a.clear();
   }

}

//848拓扑排序

#include<bits/stdc++.h>
using namespace std;
//848拓扑排序
int n,m;
const int N=1e5;
int e[N],ne[N],h[N],idx,d[N],p[N];
void add(int x,int y)
{
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}

int tuopu()
{
    queue<int>q;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!d[i])
        {
            //cout<<"000000"<<endl;
            q.push(i);
            p[cnt++]=i;
        }
    }
    while(!q.empty())
    {
        //cout<<"queue"<<endl;
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
           int u=e[i];
           d[u]--;
           if(!d[u])q.push(u),p[cnt++]=u;
        }
    }
    if(cnt==n)return 1;
    return 0;
}
int main()
{

    cin>>n>>m;
    memset(h,-1,sizeof(h));
    memset(d,0,sizeof(d));
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        d[y]++;
    }
    if(tuopu()==1)
    {
        for(int i=0;i<n;i++)
        {
            cout<<p[i]<<" ";
        }
    }
    else
    {
        cout<<-1<<endl;
    }
}