tarjan求割点与割边
洛谷P3388 【模板】割点（割顶）
解题思路：
求割点和割点数量模版，对于(u,v)如果low[v]>=dfn[u]那么u为割点,特判根结点，若根结点子树有超过一颗子树，说明根也是割点
#include<bits/stdc++.h>
using namespace std;
/* freopen("k.in", "r", stdin);
freopen("k.out", "w", stdout); */
//clock_t c1 = clock();
//std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int, int> VII;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 5e5 + 7;
const ll MAXM = 1e6 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int n, m;
int head[MAXN];
struct Edge
{
int u, v, Next;
Edge(int _u = 0, int _v = 0, int _Next = 0) { u = _u, v = _v, Next = _Next; }
} e[MAXN];
int cnt = -1;
void add(int u, int v)
{
e[++cnt].u = u;
e[cnt].v = v;
e[cnt].Next = head[u];
head[u] = cnt;
}
int dfn[MAXN], low[MAXN], dep;
int cut[MAXN];
//对于(u,v)如果low[v]>=dfn[u]那么u为割点,特判根结点，若根结点子树有超过一颗子树，说明根也是割点
void tarjan(int now, int fa)
{
dfn[now] = low[now] = ++dep;
int child = 0;
for (int i = head[now]; ~i; i = e[i].Next)
{
int v = e[i].v;
if (!dfn[v])
{
tarjan(v, fa);
low[now] = min(low[now], low[v]);
if (low[v] >= dfn[now] && now != fa)
cut[now]=1;
if (now == fa)
child++;
}
low[now] = min(low[now], dfn[v]);
}
if (child >= 2 && now == fa)
cut[now] = 1;
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, i);
int ans = 0;
for (int i = 1; i <= n; i++)
if (cut[i])
ans++;
printf("%d
", ans);
for (int i = 1; i <= n; i++)
if (cut[i])
printf("%d ", i);
printf("
");
return 0;
}
HDU-4738 Caocao's Bridges
解题思路：
裸的割边，但是有三个坑点
一：如果图不连通，不用派人去炸桥，直接输出0
二：可能会有重边
三：如果桥上没有士兵守着，那至少要派一个人去炸桥。
#include <bits/stdc++.h>
using namespace std;
/* freopen("k.in", "r", stdin);
freopen("k.out", "w", stdout); */
//clock_t c1 = clock();
//std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int, int> VII;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 5e5 + 7;
const ll MAXM = 1e6 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int n, m;
int head[MAXN];
struct Edge
{
int u, v, val, Next, flag;
Edge(int _u = 0, int _v = 0, int _val = 0, int _Next = 0, int _flag = 0) { u = _u, v = _v, v = _val, Next = _Next, flag = _flag; }
} e[MAXN << 1];
int cnt = -1;
void add(int u, int v, int val)
{
e[++cnt].u = u;
e[cnt].flag = 0;
e[cnt].val = val;
e[cnt].v = v;
e[cnt].Next = head[u];
head[u] = cnt;
}
int dfn[MAXN], low[MAXN], dep;
int cut[MAXN << 1];
//如果(u,v)是割边，当且仅当其满足low[v]>dfn[u]
int ans = inf;
void tarjan(int now, int fa)
{
dfn[now] = low[now] = ++dep;
int flag = true;
for (int i = head[now]; ~i; i = e[i].Next)
{
int v = e[i].v;
if (flag && v == fa)
{
flag = false;
continue;
}
if (!dfn[v])
{
tarjan(v, now);
low[now] = min(low[now], low[v]);
if (low[v] > dfn[now])
e[i].flag = e[i ^ 1].flag = 1;
}
low[now] = min(low[now], dfn[v]);
}
}
void init()
{
cnt = -1, dep = 0, ans = inf;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(cut, 0, sizeof(cut));
memset(head, -1, sizeof(head));
}
int main()
{
while (~scanf("%d%d", &n, &m) && n && m)
{
init();
for (int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
int k = 0;
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, -1), k++;
if (k > 1)
printf("0
");
else
{
for (int i = 0; i < cnt; i++)
if (e[i].flag)
ans = min(ans, e[i].val);
if (ans == inf)
ans = -1;
else if (ans == 0)
ans = 1;
printf("%d
", ans);
}
}
return 0;
}