输入n表示有n个变量，然后输入m个数对(u,v)，表示变量u<v。要求排列所有变量，输出任意可行解。
变量当作点，大小关系当作边，形成有向图，然后进行拓扑排序就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<iostream>
#include<cstring>
using namespace std;
const int maxn=105;
int c[maxn];
int topo[maxn],t,n,m;
bool G[maxn][maxn];
bool dfs(int u){
c[u]=-1;
for(int v=0;v<n;v++)
if(G[u][v]){
if(c[v]<0) return false;
if(!c[v]&&!dfs(v)) return false;
}
c[u]=1;
topo[--t]=u+1;
return true;
}
bool toposort(){
t=n;
memset(c,0,sizeof(c));
for(int u=0;u<n;u++)
if(!c[u])
if(!dfs(u)) return false;
return true;
}
int main(){
while(cin>>n>>m&&n){
memset(G,0,sizeof(G));
while(m--){
int i,j;
cin>>i>>j;
G[i-1][j-1]=true;
}
memset(topo,0,sizeof(topo));
if(toposort()){
for(int i=0;i<n;i++){
if(i) cout<<" ";
cout<<topo[i];
}
cout<<endl;
}
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **