这题我会。
先建圆方树。然后再跑一遍每个圆点,看看最多和几个方点相连。和超过一个方点相连的原点就是割点,注意这个图可以是不连通的,所以我们还要统计一共有几个连通块,然后只能拆一个连通块。
下面还有方法二。
代码如下:
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 10010;
const int M = 30010;
int adjList[N], adjListVcc[2*N], e[2*M], ne[2*M], idx;
int n, m;
int vccCnt;
int dfn[N], low[N], fa[N], id;
stack<int> st;
void add(int h[], int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++id;
st.push(u);
for (int i = adjList[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa[u])
continue;
if (!dfn[v]) {
fa[v] = u;
tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) {
vccCnt++;
while (1) {
int x = st.top();
st.pop();
add(adjListVcc, vccCnt, x);
add(adjListVcc, x, vccCnt);
if (x == v)
break;
}
add(adjListVcc, vccCnt, u);
add(adjListVcc, u, vccCnt);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
while (1) {
memset(adjList, -1, sizeof adjList);
memset(adjListVcc, -1, sizeof adjListVcc);
memset(e, 0, sizeof e);
memset(ne, 0, sizeof ne);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(fa, 0, sizeof fa);
st = stack<int>();
id = idx = 0;
cin >> n >> m;
if (n == 0 && m == 0)
break;
vccCnt = n;
while (m--) {
int a, b;
cin >> a >> b;
add(adjList, a+1, b+1);
add(adjList, b+1, a+1);
}
int cnt = 0;
for (int u = 1; u <= n; u++) {
if (!dfn[u]) {
tarjan(u);
cnt++;
}
}
int ans = 0;
for (int u = 1; u <= n; u++) {
int num = 0;
for (int i = adjListVcc[u]; ~i; i = ne[i]) {
int v = e[i];
if (v > n)
num++;
}
ans = max(ans, num);
}
cout << ans + cnt - 1 << endl;
}
return 0;
}
其实这题不用建圆方树。就是y老师的方法。
我们判断每个割点到底能建几个点双?就是在建圆方树的地方cnt+1,然后如果不是根的话在for结束以后再cnt+1。这样一遍就跑出来。其实这题就是找割点。然后对代码充分理解才能想到。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 10010;
const int M = 30010;
int adjList[N], adjListVcc[2*N], e[2*M], ne[2*M], idx;
int n, m;
int vccCnt;
int dfn[N], low[N], fa[N], id;
stack<int> st;
void add(int h[], int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++id;
st.push(u);
for (int i = adjList[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa[u])
continue;
if (!dfn[v]) {
fa[v] = u;
tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) {
vccCnt++;
while (1) {
int x = st.top();
st.pop();
add(adjListVcc, vccCnt, x);
add(adjListVcc, x, vccCnt);
if (x == v)
break;
}
add(adjListVcc, vccCnt, u);
add(adjListVcc, u, vccCnt);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
while (1) {
memset(adjList, -1, sizeof adjList);
memset(adjListVcc, -1, sizeof adjListVcc);
memset(e, 0, sizeof e);
memset(ne, 0, sizeof ne);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(fa, 0, sizeof fa);
st = stack<int>();
id = idx = 0;
cin >> n >> m;
if (n == 0 && m == 0)
break;
vccCnt = n;
while (m--) {
int a, b;
cin >> a >> b;
add(adjList, a+1, b+1);
add(adjList, b+1, a+1);
}
int cnt = 0;
for (int u = 1; u <= n; u++) {
if (!dfn[u]) {
tarjan(u);
cnt++;
}
}
int ans = 0;
for (int u = 1; u <= n; u++) {
int num = 0;
for (int i = adjListVcc[u]; ~i; i = ne[i]) {
int v = e[i];
if (v > n)
num++;
}
ans = max(ans, num);
}
cout << ans + cnt - 1 << endl;
}
return 0;
}