下午

#include<bits/stdc++.h>
using namespace std;

int n,m;
int x,y,ru[1005];
queue<int> q;
bool l[1005][1005];
vector<int>g[1005];
bool ans1;
int a[1005][1005];
bool b[1005];
bool d[1005][1005];
int ansn;
int kk[1005],dep[1005],xx; 

void dfs(int i){
    if(ans1==true){
        return ;
    }
    for(int j=1; j<=n; j++){
        if(a[i][j]==1 && b[j]==false && d[i][j]==false){
            if(j==ansn){
                ans1=true;
            }
            b[j]=true;
            dfs(j);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>x>>y;
        ru[x]++;
        a[y][x]=1;
        g[y].push_back(x);
    }
    for(int i=1; i<=n; i++){
        ans1=false;
        ansn=i;
        dfs(i);
        memset(b,false,sizeof(b));
        memset(d,false,sizeof(d));
        if(ans1==true){
            cout<<"Poor Xed"<<endl;
            return 0;
        }
    }
    for(int i=1; i<=n; i++){
        if(ru[i]==0){
            q.push(i);
        }
    }
    int si,tt=0;
    while(!q.empty()){
        int f=q.front();
        q.pop();
        tt++;
        si=g[f].size();
        for(int i=xx+1; i<=si+xx; i++){
            dep[i]=dep[xx]+1;
        }
        xx=si+xx;
        for(int i=0; i<g[f].size(); i++){
            int p=g[f][i];
            ru[p]--;
            if(ru[p]==0){
                q.push(p);
                kk[p]=dep[tt];
            }
        }
        
        
    }
    int jia=0;
    for(int i=1; i<=n; i++){
        jia+=kk[i];
    }
    cout<<100*n+jia<<endl;
    return 0;
}

奖金

#include<bits/stdc++.h>
using namespace std;

int n,m;
int x,y,ru[1005];
queue<int> q;
bool l[1005][1005];
vector<int>g[10005];
priority_queue<int,vector<int>,greater<int> > ans;
bool ans1;
int a[1005][1005];
bool b[1005];
bool d[1005][1005];
int ansn;

void dfs(int i){
    if(ans1==true){
        return ;
    }
    for(int j=1; j<=n; j++){
        if(a[i][j]==1 && b[j]==false && d[i][j]==false){
            if(j==ansn){
                ans1=true;
            }
            b[j]=true;
            dfs(j);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>x;
        cin>>y;
        ru[y]++;
        a[x][y]=1;
        g[x].push_back(y);
    }
    for(int i=1; i<=n; i++){
        ans1=false;
        ansn=i;
        dfs(i);
        memset(b,false,sizeof(b));
        memset(d,false,sizeof(d));
        if(ans1==true){
            cout<<"-1"<<endl;
            return 0;
        }
    }
    for(int i=1; i<=n; i++){
        if(ru[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int f=q.front();
        q.pop();
        ans.push(f);
        for(int i=0; i<g[f].size(); i++){
            int p=g[f][i];
            ru[p]--;
            if(ru[p]==0){
                q.push(p);
            }
        }
    }
    
    for(int i=0; i<n; i++){
        cout<<ans.top()<<" "; 
        ans.pop();
    }
    cout<<endl;
    return 0;
}

拓扑排序

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a1,a2;
int a[1005][1005];
bool b[1005],d[1005][1005]; 
bool ans;
int ansn;

void dfs(int i){
    if(ans==true){
        return ;
    }
    for(int j=1; j<=n; j++){
        if(a[i][j]==1 && b[j]==false && d[i][j]==false){
            if(j==ansn){
                ans=true;
            }
            b[j]=true;
            dfs(j);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>a1>>a2;
        a[a1][a2]=1;
    }
    for(int i=1; i<=n; i++){
        ansn=i;
        dfs(i);
        if(ans==true){
            cout<<"T"<<endl;
        }else cout<<"F"<<endl;
        ans=false;
        memset(b,false,sizeof(b));
        memset(d,false,sizeof(d));
    }
    return 0;
}

吃、