# 2 条题解

• @ 2017-10-24 13:47:33

仅需稍微对tarjan的求割边算法稍作改编即可。若找到一个割边，接下来就是判断这条割边是否是符合题意的割边。dfs过程中，记录子树的A服务结点数与B服务结点数，判断一下即可。

``````#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn = 100005, maxm = 100005, maxk = 10005;

int n, m, K, L, t1, t2, dfn[maxn], low[maxn], dfs_clock;
char serveA[maxn], serveB[maxn];
int head[maxn], to[maxm << 1], next[maxm << 1], lb;
int ans[maxn], idx, numA[maxn], numB[maxn];

inline void ist(int aa, int ss) {
to[lb] = ss;
++lb;
}

inline void init(void) {
memset(next, -1, sizeof next);
}

void dfs(int r, int p) {
dfn[r] = low[r] = ++dfs_clock;
numA[r] = serveA[r];
numB[r] = serveB[r];
for (int j = head[r]; j != -1; j = next[j]) {
if (to[j] == p) {
continue;
}
if (!dfn[to[j]]) {
dfs(to[j], r);
low[r] = std::min(low[r], low[to[j]]);
numA[r] += numA[to[j]];
numB[r] += numB[to[j]];
if (low[to[j]] > dfn[r]) {
if (!numA[to[j]] || !numB[to[j]] || numA[to[j]] == K || numB[to[j]] == L) {
ans[idx++] = j / 2 + 1;
}
}
}
else {
low[r] = std::min(low[r], low[to[j]]);
}
}
}

int main(void) {
//freopen("in.txt", "r", stdin);
init();
scanf("%d%d%d%d", &n, &m, &K, &L);
for (int i = 0; i < K; ++i) {
scanf("%d", &t1);
serveA[t1] = 1;
}
for (int i = 0; i < L; ++i) {
scanf("%d", &t1);
serveB[t1] = 1;
}
for (int i = 0; i < m; ++i) {
scanf("%d%d", &t1, &t2);
ist(t1, t2);
ist(t2, t1);
}

dfs(1, 0);
std::sort(ans, ans + idx);
printf("%d\n", idx);
for (int i = 0; i < idx; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}

``````
• @ 2012-11-21 18:07:53

首先缩点，缩点的过中找出割边。然后重新建一棵树，在树上跑一边dfs每棵子树的A的个数和B的个数。最后再跑一边dfs找那些子树中A[v] == 0 || B[v] == 0｜｜ A[1]

• 1

ID
1769

5

(无)

103

38

37%

2