首页 > 代码库 > 拓扑排序

拓扑排序

问题:给定几组单向边,判断是否可以拓扑排序。

输入:n   全局变量,表示点数

           g   全局变量,g[i]表示从点 i 连出去的边

输出:返回对给定的图,是否可以拓扑排序。

            L全局变量,拓扑排序的结果

 

#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int maxn=105;vector <int> g[maxn];int du[maxn],n,m,L[maxn];int toposort(){    int i,j;    memset(du,0,sizeof(du));    for(i=1; i<=n; i++)        for(j=0; j<g[i].size(); j++)            du[g[i][j]]++;    int tot=0;    queue <int> Q;    for(i=0; i<n; i++)        if(!du[i])Q.push(i);    while(!Q.empty())    {        int x=Q.front();        Q.pop();        L[tot++]=x;        for(j=0; j<g[x].size(); j++)        {            int t=g[x][j];            du[t]--;            if(!du[t])                Q.push(t);        }    }    if(tot==n)return 1;    else return 0;}int main(){    int i,j;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1; i<=100; i++)g[i].clear();        for(i=1; i<=m; i++)        {            int a,b;            scanf("%d%d",&a,&b);            g[a].push_back(b);        }        if(toposort())printf("RIGHT\n");        else printf("ERROR\n");    }    return 0;}