[UVA315]Network(tarjan, 求割点)

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=251

求割点,除了输入用strtok和sscanf处理输入以外,对于求割点的tarjan算法有了进一步理解。

特别注意88行,如果u是根并且至少两个儿子,那它一定是割点无误,还有第二个情况用如图代表:

[UVA315]Network(tarjan, 求割点)

这个例子里显然:low[4]=2,dfn[4]=4,dfn[3]=3。现dfs到3点位置了,4是3的儿子,假如3是割点,那删掉3后4和2依然连通,因此3不是割点。判断依据可以是low[4]<dfn[3]。

假如low[4]>=dfn[3]的话,那3就是割点了。

 /*
━━━━━┒ギリギリ♂ eye!
┓┏┓┏┓┃キリキリ♂ mind!
┛┗┛┗┛┃\○/
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; #define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%lld", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lrt rt << 1
#define rrt rt << 1 | 1
#define pi 3.14159265359
#define RT return
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; const int maxn = ;
char str[];
int n, m, rt, bcnt;
int G[maxn][maxn];
int dfn[maxn], low[maxn], vis[maxn];
int in[maxn];
bool cut[maxn];
vi e[maxn];
int bridge[maxn][]; void dfs(int u, int d) {
int son = ;
vis[u] = ; dfn[u] = low[u] = d;
Rep(i, e[u].size()) {
int v = e[u][i];
if(!vis[v]) {
dfs(v, d+); son++;
low[u] = min(low[u], low[v]);
if((u==rt&&son>)||(u!=rt&&low[v]>=dfn[u])) cut[u] = ;
}
else low[u] = min(low[u], dfn[v]);
}
} int main() {
// FRead();
int u, v;
while(~Rint(n) && n) {
Cls(G); Cls(dfn); Cls(low); Cls(in);
Cls(vis); Cls(bridge); Cls(cut); bcnt = ;
Rep(i, n+) e[i].cl();
getchar();
while(gets(str) && strcmp("", str)) {
char* p = strtok(str, " ");
sscanf(p, "%d", &u);
p = strtok(NULL, " ");
while(p) {
sscanf(p, "%d", &v);
p = strtok(NULL, " ");
G[u][v] = G[v][u] = ;
}
}
For(i, , n+) {
For(j, i+, n+) {
if(G[i][j]) {
e[i].push_back(j);
e[j].push_back(i);
}
}
}
rt = ;
int ret = ;
dfs(, );
For(i, , n+) if(cut[i]) ret++;
printf("%d\n", ret);
}
RT ;
}
上一篇:Network -UVa315(连通图求割点)


下一篇:2018年3月份的PTA(一)