正题
题目链接:https://www.luogu.com.cn/problem/P4782
题目大意
给若干个条件限定为
x
i
为
a
或
x
j
为
b
x_i为a或x_j为b
xi为a或xj为b。求构造一个序列
x
x
x满足所有条件
解题思路
我们对于每个
x
i
x_i
xi构造两个点分别表示
x
i
x_i
xi为
0
/
1
0/1
0/1。然后就开始对能够确定的条件关系连边。那么显然有在一个强连通分量里的真假一定相等。也就是如果对于一个
x
i
x_i
xi的两个点都在一个强连通里，那么就无解了。
而确定之后我们只需要根据拓扑序大小来确定真假即可。
时间复杂度
O
(
n
)
O(n)
O(n)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std
;
const int N
=2e6+10;
struct node
{
int to
,next
;
}a
[N
*2];
int n
,m
,tot
,cnt
,num
,ls
[N
];
int dfn
[N
],low
[N
],color
[N
];
bool ins
[N
];
stack
<int> S
;
void addl(int x
,int y
){
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
return;
}
void tarjan(int x
){
dfn
[x
]=low
[x
]=++cnt
;
S
.push(x
);ins
[x
]=1;
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
if(!dfn
[y
])tarjan(y
),low
[x
]=min(low
[x
],low
[y
]);
else if(ins
[y
]) low
[x
]=min(low
[x
],dfn
[y
]);
}
if(low
[x
]==dfn
[x
]){
++num
;
while(S
.top()!=x
){
ins
[S
.top()]=0;
color
[S
.top()]=num
;
S
.pop();
}
color
[S
.top()]=num
;
ins
[S
.top()]=0;
S
.pop();
}
return;
}
int main()
{
scanf("%d%d",&n
,&m
);
for(int k
=1;k
<=m
;k
++){
int i
,a
,j
,b
;
scanf("%d%d%d%d",&i
,&a
,&j
,&b
);
addl(i
+a
*n
,j
+(!b
)*n
);
addl(j
+b
*n
,i
+(!a
)*n
);
}
for(int i
=1;i
<=n
*2;i
++)
if(!dfn
[i
])tarjan(i
);
for(int i
=1;i
<=n
;i
++)
if(color
[i
]==color
[i
+n
]){
printf("IMPOSSIBLE");
return 0;
}
printf("POSSIBLE\n");
for(int i
=1;i
<=n
;i
++)
printf("%d ",color
[i
]<color
[i
+n
]);
}
