TopSort拓扑排序 邻接表 优先队列实现字典序

//TopSort拓扑排序 邻接表 优先队列实现字典序
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define why 100005
struct node
{
    int next,to;
}a[500005];
int h[why],cnt,n,In[why],ans[why],m;
priority_queue<int,vector<int>,greater<int> >q;
inline void Add(int x,int y)
{
    cnt++;
    a[cnt].to=y;
    a[cnt].next=h[x];
    h[x]=cnt;
}
inline int redn()
{
    int ret=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return f>0?ret:-ret;
}
inline bool TopSort()
{
    register int i,u;
    int t=0,now,y;
    for(i=1;i<=n;++i)if(!In[i])q.push(i);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        ans[++ans[0]]=now;
        ++t;
        for(u=h[now];u;u=a[u].next)
        {
            y=a[u].to;
            --In[y];
            if(!In[y])q.push(y);
        }
    }
    return (t==n);
}
int main()
{
    register int i;
    int _1,_2;
    n=redn();
    m=redn()+1;
    while(--m)
    {
        _1=redn();
        _2=redn();
        Add(_1,_2);
        ++In[_2];
    }
    if(TopSort())for(i=1;i<=ans[0];++i)printf("%d ",ans[i]);
    else printf("NO SOLUTION");
    return 0;
}

 

上一篇:L1-Day8


下一篇:BSOJ1004 -- 【TYVJ1071】LCIS最长公共上升子序列