hdu 3594 Cactus

本文从WordPress迁移而来, 查看全部WordPress迁移文章

有向图的仙人掌图的判定,详细分析请看:仙人掌图的判定

主要就是在tarjan中设置判断来剪枝,遇到不符合cactus的条件立即返回

不过据说这题的数据很水,不能很好地测试模板

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
1.建图
2.tarjan求scc
tarjan过程中判断是否有横叉边,若有直接递归返回false
同时tarjan过程中就可以维护son[],back[]数组,当一个点u的a[u],b[u]不满足cactus要求时直接返回
3.好好理解 树边,横叉边,后向边
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 20010
#define M 50010
#define cl memset

int n,tot;
int head[N];
struct edge{
int v,next;
}e[M];
int dfn[N],low[N],dcnt;
int belong[N],bcnt;
int stack[N],top;
bool ins[N],vis[N];
int son[N],back[N];

inline void add(int u ,int v){
e[tot].v = v;
e[tot].next = head[u];
head[u] = tot++;
}

bool tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u;
ins[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(vis[v]) return false; //横叉边
if(!dfn[v]){ //树边
bool ok = tarjan(v);
if(!ok) return false; //剪枝
low[u] = min(low[u],low[v]);
if(low[v] < dfn[u]) son[u]++;
if(son[u] >= 2) return false;
}
else if(ins[v]){
low[u] = min(low[u],dfn[v]);
back[u]++;
if(back[u] >= 2) return false;
}
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
ins[x] = false;
belong[x] = bcnt;
if(x == u) break;
}
}
vis[u] = true;
if(son[u] + back[u] >= 2)
return false;
return true;
}

void scc(){
dcnt = bcnt = top = 0;
cl(son,0,sizeof(son));
cl(back,0,sizeof(back));
cl(dfn,0,sizeof(dfn));
cl(ins,false,sizeof(ins));
cl(vis,false,sizeof(vis));

bool ok = true;
for(int i = 0; i < n; i++)
if(!dfn[i]){
ok = tarjan(i);
if(!ok || bcnt > 1){
ok = false; break;
}
}
if(ok) puts("YES");
else puts("NO");
}

int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
cl(head,-1,sizeof(head));
tot = 0;
while(true){
int u,v;
scanf("%d%d",&u,&v);
if(u == 0 && v == 0) break;
add(u,v);
}
scc();
}
return 0;
}