tarjan-割点-割边（桥）1
基础
割点（割顶）：删除一个点，图的联通分量增加，这个点就是割点。
割边（桥）：删除一个边，图的联通分量增加，这个边就是割点。
例题
P3388 【模板】割点（割顶）
对于儿子能会到的点大于等于现在的点，且儿子个数大于二也不是根节点就是。
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
string s=#__VA_ARGS__,s2="";\
vector<string>v;\
for(auto i:s){\
if(i==','){\
v.push_back(s2);\
s2="";\
}else{\
s2+=i;\
}\
}\
v.push_back(s2);\
vector<int>v2={__VA_ARGS__};\
for(int i=0;i<v.size()-1;i++){\
cout<<v[i]<<"="<<v2[i]<<"\n";\
}\
cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 2e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
struct node
{
int v , nxt ;
}edge[kMaxN] ;
int n , m , tim , cnt , res , root ;
int color[kMaxN] , dfn[kMaxN] , low[kMaxN] , head[kMaxN] ;
bool vis[kMaxN] ;
inline ll ksm(ll a , ll b)
{
ll mul = 1 ;
while(b)
{
if(b & 1) mul *= a , mul %= MOD ;
a *= a ;
a %= MOD ;
b >>= 1 ;
}
return mul ;
}
inline int read()
{
int x = 0 , f = 1 ;
char ch = getchar() ;
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1 ;
ch = getchar() ;
}
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
return x * f ;
}
void write(int x)
{
if(x < 0) putchar('-') , x = -x ;
if(x > 9) write(x / 10) ;
putchar(x % 10 + '0') ;
}
void tanjan(int u)
{
dfn[u] = low[u] = ++tim ;
int ans = 0 ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dfn[v] == 0)
{
tanjan(v) ;
low[u] = min(low[u] , low[v]) ;
if(low[v] >= dfn[u])
{
ans++ ;
if(u != root || ans >= 2) vis[u] = 1 ;
}
}
else
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
void add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void work()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
add_edge(u , v) ;
add_edge(v , u) ;
}
for( int i = 1 ; i <= n ; i++ )
{
if(dfn[i] == 0)
{
root = i ;
tanjan(i) ;
}
}
for( int i = 1 ; i <= n ; i++ )
{
if(vis[i]) res++ ;
}
cout << res << "\n" ;
for( int i = 1 ; i <= n ; i++ )
{
if(vis[i])
{
cout << i << " " ;
}
}
}
signed main()
{
// freopen(".in" , "r" , stdin) ;
// freopen(".out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}
HDU4738 Caocao's Bridges
就是求割点的边的最小值即可。
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
string s=#__VA_ARGS__,s2="";\
vector<string>v;\
for(auto i:s){\
if(i==','){\
v.push_back(s2);\
s2="";\
}else{\
s2+=i;\
}\
}\
v.push_back(s2);\
vector<int>v2={__VA_ARGS__};\
for(int i=0;i<v.size()-1;i++){\
cout<<v[i]<<"="<<v2[i]<<"\n";\
}\
cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 1e3 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
struct node
{
int v , w , nxt ;
}edge[kMaxN * kMaxN * 2] ;
int n , m , tim , cnt , ans ;
int dfn[kMaxN] , low[kMaxN] , head[kMaxN] ;
inline ll ksm(ll a , ll b)
{
ll mul = 1 ;
while(b)
{
if(b & 1) mul *= a , mul %= MOD ;
a *= a ;
a %= MOD ;
b >>= 1 ;
}
return mul ;
}
inline int read()
{
int x = 0 , f = 1 ;
char ch = getchar() ;
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1 ;
ch = getchar() ;
}
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
return x * f ;
}
void write(int x)
{
if(x < 0) putchar('-') , x = -x ;
if(x > 9) write(x / 10) ;
putchar(x % 10 + '0') ;
}
void tanjan(int u , int fa)
{
dfn[u] = low[u] = ++tim ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(dfn[v] == 0)
{
tanjan(v , i ^ 1) ;
low[u] = min(low[u] , low[v]) ;
if(low[v] > dfn[u])
{
ans = min(ans , edge[i].w);
}
}
else if(i != fa)
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
void add_edge(int u , int v , int w)
{
edge[++cnt] = {v , w , head[u]} ;
head[u] = cnt ;
}
void work()
{
while(cin >> n >> m && n)
{
tim = cnt = ans = 0 ;
cnt++ ;
memset(head , 0 , sizeof head) ;
memset(dfn , 0 , sizeof dfn) ;
memset(low , 0 , sizeof low) ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v , w ;
cin >> u >> v >> w ;
add_edge(u , v , w) ;
add_edge(v , u , w) ;
}
ans = INF ;
tanjan(1 , 0) ;
if(ans == INF) cout << "-1\n" ;
else if(tim != n) cout << "0\n" ;
else if(ans == 0) cout << "1\n" ;
else cout << ans << "\n" ;
}
}
signed main()
{
// freopen(".in" , "r" , stdin) ;
// freopen(".out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}
U132350 【模板】割边（桥）
和割点相似。
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
string s=#__VA_ARGS__,s2="";\
vector<string>v;\
for(auto i:s){\
if(i==','){\
v.push_back(s2);\
s2="";\
}else{\
s2+=i;\
}\
}\
v.push_back(s2);\
vector<int>v2={__VA_ARGS__};\
for(int i=0;i<v.size()-1;i++){\
cout<<v[i]<<"="<<v2[i]<<"\n";\
}\
cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 2e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
int u , w ;
};
struct Edgeve
{
int v , w ;
};
struct node
{
int v , nxt ;
}edge[kMaxN] ;
int n , m , tim , cnt , res ;
int color[kMaxN] , dfn[kMaxN] , low[kMaxN] , head[kMaxN] ;
bool vis[kMaxN] ;
inline ll ksm(ll a , ll b)
{
ll mul = 1 ;
while(b)
{
if(b & 1) mul *= a , mul %= MOD ;
a *= a ;
a %= MOD ;
b >>= 1 ;
}
return mul ;
}
inline int read()
{
int x = 0 , f = 1 ;
char ch = getchar() ;
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1 ;
ch = getchar() ;
}
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
return x * f ;
}
void write(int x)
{
if(x < 0) putchar('-') , x = -x ;
if(x > 9) write(x / 10) ;
putchar(x % 10 + '0') ;
}
void tanjan(int u , int fa)
{
dfn[u] = low[u] = ++tim ;
for( int i = head[u] ; i ; i = edge[i].nxt )
{
int v = edge[i].v ;
if(v == fa) continue ;
if(dfn[v] == 0)
{
tanjan(v , u) ;
low[u] = min(low[u] , low[v]) ;
if(low[v] > dfn[u])
{
res++ ;
}
}
else
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
void add_edge(int u , int v)
{
edge[++cnt] = {v , head[u]} ;
head[u] = cnt ;
}
void work()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int u , v ;
cin >> u >> v ;
add_edge(u , v) ;
add_edge(v , u) ;
}
for( int i = 1 ; i <= n ; i++ )
{
if(dfn[i] == 0)
{
tanjan(i , 0) ;
}
}
cout << res << "\n" ;
}
signed main()
{
// freopen(".in" , "r" , stdin) ;
// freopen(".out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--) work() ;
return 0 ;
}