拓扑排序 C++ 代码

拓扑排序 C++ 代码

/*
*Program:TopologicalSort
*Author:Yee-fan Zhu
*/
#include <fstream>
using namespace std;
ifstream fin("topo.in");
ofstream fout("topo.out");
bool TopologicalSort(int a[][101],int *ans) //可以完成拓扑排序则返回True 　　
{
        int n = a[0][0], i, j;
        int into[101];
        memset(into, 0, sizeof(into));
        memset(ans, 0, sizeof(ans));
        //计算每个顶点的入度
        for (i=1;i<=n;i++)
        {
                for (j=1;j<=n;j++)
                {
                        if (a[i][j]>0)
                                into[j]++;
                }
        }
        into[0]=1;
        for (i=1;i<=n;i++)
        {
                j=0;
                while (into[j]!= 0)
                {
                        j++;
                        if(j>n)
                        return false;
                }
                ans[i]=j;
                into[j]=-1;
                //删除这个顶点
                for (int k=1; k<=n; k++)
                {
                        if (a[j][k]>0)
                                into[k]--;
                }
        }
        return true;
}
int main()
{
        int n;
        int mat[101][101];
        int ans[101];
        fin>>n;
        mat[0][0]=n;
        for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                        mat[i][j]=0;
        int m;
        fin>>m;
        int x,y,z;
        for (int i=0;i<m;i++)
        {
                fin>>x>>y>>z;
                mat[x][y]=z;
        }
        if (TopologicalSort(mat,ans))
        {
                fout<<"succeed"<<endl;
                        for (int i=1;i<=n;i++)
                        {
                                fout<<ans[i]<< " ";
                        }
                        fout<<endl;
        }
        else fout<<"failed"<<endl;
        return 0;
}