拓扑排序

拓扑排序一般情况:一个直观的算法就是每次删除一个入度为0的点，直到没有入度为0的点为止

hihocoder-1174

#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long ll;
const int N=100000+20;
const int M=500000+20;
int first[N],tot,in[N],n,m,cnt;
struct edge
{
    int v,next;
} e[M];
void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}
void topsort()
{
    queue<int>q;
    for(int i=1; i<=n; i++)
        if(!in[i])
            q.push(i);
    while(!q.empty())
    {
        cnt++;
        int u=q.front();
        q.pop();
        for(int i=first[u]; ~i; i=e[i].next)
        {
            int v=e[i].v;
            if(!--in[v])
                q.push(v);
        }
    }
}
void init()
{
    mem(first,-1);
    mem(in,0);
    tot=0;
    cnt=0;
}
int main()
{
    int t,u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            add_edge(u,v);
            in[v]++;
        }
        topsort();
        puts(cnt==n?"Correct":"Wrong");//用cnt判断是否删完了
    }
    return 0;
}

HDU4857 逃生(拓扑排序)

因为要把最小的输出，我们需要反向建边，逆序输出，需要用到一个优先队列。

关于为什么要反向：blog.csdn.net/u012861385/article/details/38059515

拓扑排序的顺序：

找出入度为0的点，然后把这个点记录下来，然后删去这个点以及它的所有出边，以此类推，直到删去所有的点为止

int n,m,len,k;  
struct node  
{  
    int v,next;  
} E[M];  
int first[N],vis[N],path[N];  
void add_edge(int u,int v)  
{  
    E[len].v=v;  
    E[len].next=first[u];  
    first[u]=len++;  
}  
void toposort()  
{  
    k=0;  
    priority_queue<int>q;  
    for(int i=1; i<=n; i++)  
        if(!vis[i])  
            q.push(i);//找出入度为0的顶点，放进优先队列  
    while(!q.empty())  
    {  
        int u=q.top();  
        q.pop();  
        path[k++]=u;//记录顺序  
        for(int i=first[u]; i!=-1; i=E[i].next)  
        {  
            int v=E[i].v;  
            vis[v]--;//删除边  
            if(!vis[v])  
                q.push(v);//如果入度为0，继续删去  
        }  
    }  
}  
int main()  
{  
    int u,v,t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        len=0;  
        scanf("%d%d",&n,&m);  
        mem(first,-1);  
        for(int i=0; i<m; i++)  
        {  
            scanf("%d%d",&u,&v);  
            add_edge(v,u);  
            vis[u]++;//记录入度  
        }  
        toposort();  
        for(int i=k-1; i>=0; i--)  
        {  
            printf("%d",path[i]);  
            if(i)printf(" ");  
        }  
        puts("");  
    }  
    return 0;  
}

拓扑排序判环:

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
const int N = 1e5 + 10;
vector<int> e[N];
int vis[N], n;
int dfs(int u)
{
    vis[u] = -1;
    for (auto v : e[u])
    {
        if (vis[v] < 0)
            return 0;
        else if (!vis[v] && !dfs(v))
            return 0;
    }
    vis[u] = 1;
    return 1;
}
int topsort()
{
    mem(vis, 0);
    for (int u = 1; u <= n; u++)
        if (!vis[u])
            if (!dfs(u))
                return 0;
    return 1;
}
int main()
{
    //读入+加边
    puts(topsort() ? "无环" : "有环");
    return 0;
}