拓扑排序的小总结

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100 + 15;
int n,m,t;//图中有n个节点
int topo[maxn];//储存拓扑排序的顺序
int staus[maxn];//表示转态
bool Grape[maxn][maxn];//表示依赖关系
bool dfs(int u)
{
    staus[u] = -1;//表示正在进行深搜
    for(int v=1;v<=n;++v)
    {
        if(Grape[u][v])
        {
            if(staus[v]<0)
                return false;//说明存在环
            if(!staus[v]&&!dfs(v))//如果未被访问过
                return false;
        }
    }
    staus[u] = 1;//表示已经深搜完并返回的状态
    topo[--t] = u;
    return true;
}
bool topoSort()
{
    t = n;
    memset(staus,0,sizeof(staus));//节点都未被访问过
    for(int u=1;u<=n;++u)//深搜每一个节点
    {
        if(!staus[u])//当未访问过
            if(!dfs(u))
                return false;
    }
    return true;
}
int main()
{
    while(cin>>n>>m)
    {
        memset(Grape,false,sizeof(Grape));
        if(n==0&&m==0)
            break;  
        int u,v;
        for(int i=0;i!=m;++i)
        {
            cin>>u>>v;
            Grape[u][v] = true;
        }
        topoSort();
        cout<<topo[0];
        for(int i=1;i!=n;++i)
            cout<<" "<<topo[i];
        cout<<endl;
    }
}

UVA 10305

POJ 1094

#include<iostream>//拓扑排序
#include<cstdio>//因为只需要判断欧拉道路,所以每次去掉当前节点总存在一入度为1的节点(important)
#include<cstring>
using namespace std;
const int maxn = 35;
int n,m;//n个节点,m个询问
bool Grape[maxn][maxn];//依赖关系
int indegree[maxn];//统计入度的多少
int tmp[maxn];//暂存入度
char Sort[maxn];
int tuopuSort(int n)//返回状态
{
    int pos = 0,cur = 0;//入度为0的节点的坐标
    int flag = 1;
    for(int i=1;i<=n;++i)
        tmp[i] = indegree[i];
    for(int i=1;i<=n;++i)
    {
        int num = 0;//每次取出一个入度为0的节点
        for(int j=1;j<=n;++j)
        {
            if(tmp[j]==0)//入度为0
            {
                ++num;//入度节点个数
                pos = j;
            }
        }
        if(num==0)
            return 0;//存在环
        if(num>1)
            flag = -1;//不能确定(可能存在环，题目要求先判断环)（important）
        Sort[cur++] = pos + 'A' - 1;
        tmp[pos] = -1;
        for(int j=1;j<=n;++j)
            if(Grape[pos][j])
                --tmp[j];//减少入度 
    }
    return flag;//成功
}
int main()
{
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        memset(Grape,false,sizeof(Grape));
        memset(indegree,0,sizeof(indegree));
        char ch1,ch2,op;//ch1 -> ch2存在边表示依赖关系
        int staus = -1;
        bool flag = false;
        for(int i=1;i<=m;++i)
        {
            cin>>ch1>>op>>ch2;
            if(staus==0||staus==1)
                continue;
            Grape[ch1-'A'+1][ch2-'A'+1] = true;
            ++indegree[ch2-'A'+1];//入度加一
            staus = tuopuSort(n);
            if(staus==0)
            {
                cout<<"Inconsistency found after "<<i<<" relations."<<endl;
                flag = true;
            }
            if(staus==1)
            {
                cout<<"Sorted sequence determined after "<<i<<" relations: ";
                for(int j=0;j!=n;++j)
                    cout<<Sort[j];
                cout<<"."<<endl;
                flag = true;
            }
        }
        if(!flag)
            cout<<"Sorted sequence cannot be determined."<<endl;
    }
}

呜呜呜，菜死了