/*
三维拓扑排序
将每个长方体分解成六个面，xyz三维进行操作
每一维上的的所有长方体的面都应该服从拓扑关系，即能够完成拓扑排序=如果两个长方体的关系时相交，那么其对应的三对面只要交叉即可 如 a1 b1 a2 b2反之对应的那对面不可以交叉 如a1 a2 b1 b2
同时长方体自身的对应两个面也具有拓扑关系
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
struct Edge{
int to,nxt;}edge[
3][maxn*
100];
int head[
3][maxn],tot[
3],
in[
3][maxn],pos[
3][maxn];
int n,m;
void init(){
memset(head,-
1,
sizeof head);
tot[0]=tot[
1]=tot[
2]=
0;
}
void addedge(
int k,
int u,
int v){
edge[k][tot[k]].to=
v;
edge[k][tot[k]].nxt=
head[k][u];
head[k][u]=tot[k]++
;
}
int solve(
int k){
//对第k维上的面进行拓扑排序
int cnt=
0;
queue<
int>
q;
for(
int i=
1;i<=n*
2;i++
)
if(
in[k][i]==
0)
q.push(i);
while(!
q.empty()){
int u=
q.front();
q.pop();
cnt++
;
for(
int i=head[k][u];i!=-
1;i=
edge[k][i].nxt){
int v=
edge[k][i].to;
in[k][v]--
;
if(
in[k][v]==
0){
q.push(v);
pos[k][v]=pos[k][u]+
1;
}
}
}
if(cnt==
2*n)
return 1;
else return 0;
}
int main(){
int tt=
0;
while(cin>>n>>m &&
n){
init();
memset(in,
0,
sizeof in);
memset(pos,0,
sizeof pos);
for(
int i=
0;i<
3;i++)
//每个长方体自身的约数
for(
int j=
1;j<=n;j++
){
in[i][j+n]++
;
addedge(i,j,j+
n);
}
while(m--
){
char ch;
int u,v;
cin>>ch>>u>>
v;
if(ch==
'I'){
for(
int i=
0;i<
3;i++
){
in[i][u+n]++
;
addedge(i,v,u+
n);
in[i][v+n]++
;
addedge(i,u,v+
n);
}
}
else {
in[ch-
'X'][v]++
;
addedge(ch-
'X',u+
n,v);
}
}
int ans0=solve(
0);
int ans1=solve(
1);
int ans2=solve(
2);
if(ans1==
0 || ans2==
0 || ans0==
0){
printf("Case %d: IMPOSSIBLE\n\n",++
tt);
continue;
}
printf("Case %d: POSSIBLE\n",++
tt);
for(
int i=
1;i<=n;i++
){
printf("%d %d %d ",pos[
0][i],pos[
1][i],pos[
2][i]);
printf("%d %d %d\n",pos[
0][i+n],pos[
1][i+n],pos[
2][i+
n]);
}
puts("");
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10451069.html
相关资源：拓扑构建二维网络数据集和拓扑构建三维网络数据集
