Description:
@card{
给定一个$n$个点$m$条边的有向图,现在要求图中任意两点$u$和$v$,均可满足$u$能通往$v$或$v$能通往$u$,请你判断要求是否能够成立。
$O(n)$
}
Solution:
@card{
看一下数据范围,发现$O(nm)$能过,那我们可以打个暴力,并AC本题(雾)。
再看一下数据,多组数据,可能会有毒瘤出题人$n$组数据卡我,那我们缩点以后上个bitset优化一下暴力,并AC本题。缩点后建正反图,做两遍”可达性统计”,最后或起来,考虑每个点是否能到达所有点即可。跑的比部分$O(n)$算法还快。
说正经的,这个问题显然可以缩点变成一个有向无环图上的等价问题,考虑其拓扑序,显然对一个点,它需要能到达所有拓扑序在它后面的节点。
于是我们就有一个结论,一个有向无环图满足题意,当且仅当它有唯一的拓扑序。
如何理解?拓扑序描述了节点之间的”先后关系”,如果一个节点$b$需要在节点$a$之后进行计算,即$b$的拓扑序在$a$之后,那么从$a$出发一定至少有一条路径到$b$。但是我们平时随手写的拓扑排序会出现存在几个节点之间,没有”先后关系”,先计算哪个都无所谓,那么这些节点之间的顺序调换就会产生不同的拓扑序,即这些节点不能互相到达,不满足题意。
具体代码实现可以在bfs时判断是否一次扫描后有多个节点同时入队,虽然我们在tarjan的过程中其实已经求出了一个逆拓扑序。
}
Code:
@card{
// bitset优化暴力
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#define rint register int
#define lint long long
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline void readint(tint& x) {
int f = 1; char ch = getchar(); x = 0;
for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
using namespace std;
const int maxn = 1e3 + 10;
const int maxm = 100000 + 10;
struct Graph{
bool vis[maxn];
bitset<maxn> dp[maxn];
int head[maxn], ev[maxm], nxt[maxm], totedge;
inline void addedge(int nu, int nv) {
ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
}
void clear(int n) {
memset(head, 0, sizeof(head)), totedge = 1;
for(rint i=1; i<=n; i++) dp[i].reset();
memset(vis, 0, sizeof(vis));
}
void dfs(int x) {
if(vis[x]) return;
vis[x] = 1, dp[x][x] = 1;
for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
dfs(y), dp[x] |= dp[y];
}
}
}g2, g3;
namespace G1{
int n, m;
int head[maxn], ev[maxm], nxt[maxm], totedge = 1;
inline void addedge(int nu, int nv) {
ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
}
int dcc_id[maxn], totdcc = 0;
int low[maxn], dfn[maxn], totdfn = 0;
int s[maxn], stop = 0;
int cnt_in[maxn], cnt_out[maxn];
void clear() {
memset(cnt_in, 0, sizeof(cnt_in)), memset(cnt_out, 0, sizeof(cnt_out));
memset(dfn, 0, sizeof(dfn)), memset(dcc_id, 0, sizeof(dcc_id));
memset(head, 0, sizeof(head));
g2.clear(totdcc), g3.clear(totdcc);
totdcc = totdfn = stop = totedge = 0;
}
void dfs(int x) {
low[x] = dfn[x] = ++totdfn, s[++stop] = x;
for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
if(dfn[y] == 0) dfs(y), low[x] = min(low[x], low[y]);
else if(dcc_id[y] == 0) low[x] = min(low[x], dfn[y]);
}
if(low[x] == dfn[x]) {
++totdcc;
do {
int z = s[stop]; dcc_id[z] = totdcc;
for(rint i=head[z], y=ev[i]; i; i=nxt[i], y=ev[i]) {
if(dcc_id[y] && dcc_id[y] != totdcc) {
g2.addedge(totdcc, dcc_id[y]), g3.addedge(dcc_id[y], totdcc);
cnt_in[dcc_id[y]]++, cnt_out[totdcc]++;
}
}
} while(s[stop--] != x);
}
}
void work() {
int T = 0;
readint(T);
while(T--) {
readint(n), readint(m);
int nu, nv;
while(m--) {
readint(nu), readint(nv);
addedge(nu, nv);
}
for(rint x=1; x<=n; x++) if(dfn[x] == 0) dfs(x);
int cnt_zero_in = 0, cnt_zero_out = 0;
for(rint t=1; t<=totdcc; t++)
cnt_zero_in += (cnt_in[t] == 0), cnt_zero_out += (cnt_out[t] == 0);
if(cnt_zero_in == 1 && cnt_zero_out == 1) {
g2.dfs(totdcc), g3.dfs(1);
bitset<maxn> full;
for(rint i=1; i<=totdcc; i++) full[i] = 1;
bool failed = 0;
for(rint t=1; t<=totdcc; t++)
if((g2.dp[t] | g3.dp[t]) != full) { failed = 1; break; }
puts(failed ? "No" : "Yes");
} else puts("No");
clear();
}
}
};
int main() {
G1::work();
return 0;
}
// 正解
#include <iostream>
#include <cstdio>
#include <cstring>
#define rint register int
#define lint long long
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline void readint(tint& x) {
int f = 1; char ch = getchar(); x = 0;
for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
using namespace std;
const int maxn = 1000 + 10;
const int maxm = 6000 + 10;
namespace G2{
int head[maxn], ev[maxm], nxt[maxm], totedge = 1;
int cnt_in[maxn];
inline void addedge(int nu, int nv) {
ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
cnt_in[nv]++;
}
int q[maxn];
void clear(int n) {
memset(head, 0, sizeof(int) * (n + 1)), totedge = 1;
memset(cnt_in, 0, sizeof(int) * (n + 1));
}
bool check(int n) {
int l = 1, r = 0, cnt = 0;
for(rint x=1; x<=n; x++) if(cnt_in[x] == 0) cnt++; // 如果图中有多个流图,dcc序不连续
if(cnt > 1) return 0;
q[++r] = n;
while(l <= r) {
int x = q[l++], cnt = 0;
for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
if(--cnt_in[y] == 0) q[++r] = y, cnt++;
}
if(cnt > 1) return 0;
}
return 1;
}
};
namespace G1{
int n, m;
int head[maxn], ev[maxm], nxt[maxm], totedge = 1;
inline void addedge(int nu, int nv) {
ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
}
int dcc_id[maxn], totdcc = 0;
int dfn[maxn], low[maxn], totdfn = 0;
int s[maxn], stop = 0;
void clear() {
memset(head, 0, sizeof(int) * (n + 1));
memset(dcc_id, 0, sizeof(int) * (n + 1));
memset(dfn, 0, sizeof(int) * (n + 1));
G2::clear(totdcc);
totdcc = totdfn = totedge = stop = 0;
}
void dfs(int x) {
dfn[x] = low[x] = ++totdfn, s[++stop] = x;
for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
if(dfn[y] == 0) dfs(y), low[x] = min(low[x], low[y]);
else if(dcc_id[y] == 0) low[x] = min(low[x], dfn[y]);
}
if(low[x] == dfn[x]) {
++totdcc;
do {
int z = s[stop]; dcc_id[z] = totdcc;
for(rint i=head[z], y=ev[i]; i; i=nxt[i], y=ev[i]) {
if(dcc_id[y] && dcc_id[y] != totdcc) G2::addedge(totdcc, dcc_id[y]);
}
} while(s[stop--] != x);
}
}
void work() {
int T = 0;
readint(T);
while(T--) {
readint(n), readint(m);
int nu, nv;
while(m--) {
readint(nu), readint(nv);
addedge(nu, nv);
}
for(rint x=1; x<=n; x++) if(dfn[x] == 0) dfs(x);
puts(G2::check(totdcc) ? "Yes" : "No");
clear();
}
}
};
int main() {
G1::work();
return 0;
}
}
原来如此%%%
%%%夏日大佬