拓扑排序模板

thomas_zjl · 2020-10-24 11:27:30 · 个人记录

给自己看的

#include<bits/stdc++.h>
using namespace std;
long long x,y;
long long n,m;
long long In[1001];
long long b[1001];
bool f[1001];
long long F[1001][1001];
inline void Print() 
{
    for(int i=1;i<n;i++) 
    {
        printf("%d ",b[i]);
    }
    printf("%d\n",b[n]);
}
inline void dfs(int step)
{
    if(step>n)
    {
        Print();
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if((In[i]==0)&&(f[i]==1))
        {
            f[i]=0;
            for(int j=1;j<=n;j++) 
            {
                if(F[i][j]==1) 
                {
                    In[j]--;
                }
            }
            b[step]=i;
            dfs(step+1);
            for(int j=1;j<=n;j++) 
            {
                if(F[i][j]==1)
                {
                    In[j]++;
                }
            }
            f[i]=1;
        }
    }
}
int main() 
{
    scanf("%d%d",&n,&m);
    memset(F,0,sizeof(F));
    memset(f,1,sizeof(f));
    for(int i=1;i<=m;i++)
     {
        scanf("%d%d",&x,&y);
        F[x][y]=1;
        In[y]++;
    }
    dfs(1);
    return 0;
}