图论 cactus 专题
仰翔
一 . 有向图cactus判定
uva 10510
思路：
方法一：
1.不能有横向边（也就是不指向祖先也不指向子孙节点的边）
2.设 y1 为 x 的儿子节点，满足 low[ y1 ] < dfn[x] 的 y1的个数为 m
设 y2为 x 的父亲节点 ，个数为n
则 m + n < 2
3.联通块的个数为1
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 20000 + 100;
const LL maxm = 20000 + 100;
LL n,m,scc,dfn[maxn],low[maxn],tim,c[maxn],fa[maxn],inst[maxn],in[maxn],out[maxn];
vector<LL> G[maxn];
void init(){
for( LL i = 0;i< n;i++ ){
dfn[i] = c[i] = inst[i] = in[i] = out[i] = 0;
G[i].clear();
}
scc = 0;
tim = 0;
fa[0] = -1;
}
void add( LL x,LL y ){
G[x].push_back( y );
}
bool tarjan(LL x){
inst[x] = 1;
LL cnt = 0;
dfn[x] = low[x] =++tim;
for( LL i = 0;i < G[x].size();i++ ){
LL y = G[x][i];
if( dfn[y] && dfn[y] < dfn[x] && !inst[y] ) return false; // 横向边判定
if(!dfn[y]){
if(!tarjan( y )) return false;
low[x] = min( low[x],low[y] );
if( low[y] < dfn[x] ){
cnt++;
}
}else if( inst[y] ){ // 处理前向边
low[x] = min( low[x],dfn[y] );
cnt++;
}else if(!inst[y] ){ //处理后向边
if( low[y] < dfn[x] ){
cnt++;
}
}
}
inst[x] = 0;
if( cnt > 1) return false;
if( dfn[x] == low[x] ){ // 处理联通块，注意这里的low数组只能通过前向边和后向边更新，不
scc++; // 能通过横向边更新（遇到横向边直接return false 了），所以
if( scc > 1 ) return false;// 这 里low数组的值与普通tarjan算法求出的值是一样的
}
return true;
}
bool judge( ){
for( LL i = 0;i < n;i++ ){
if( dfn[i] ) continue;
if(!tarjan(i)) return false;
}
return true;
}
int main()
{
//freopen( "123.txt","r",stdin );
LL T,x,y;
scanf("%lld",&T);
while( T-- ){
scanf("%lld%lld",&n,&m);
init();
for(LL i = 0;i < m;i++){
scanf("%lld%lld",&x,&y);
in[y]++;
out[x]++;
add( x,y );
}
if( judge() ){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
方法二：
有向cactus图可以理解为 若干个圈组成，并且这些圈两两之间的交集最多为一个点。这使我们联想到欧拉回路。欧拉回路是若干个边不重的圈的交集，但圈与圈两两之间可以相交于2个点。由此我们可以得出cactus图是欧拉图的子集。
由此我们可以的出方法二，先判定欧拉图，再判定是否有圈与圈之间相交于两个点的情况。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 20000 + 100;
const LL maxm = 20000 + 100;
LL n,m,dfn[maxn],c[maxn],fa[maxn],inst[maxn],in[maxn],out[maxn];
vector<LL> G[maxn];
void init(){
for( LL i = 0;i< n;i++ ){
dfn[i] = c[i] = inst[i] = in[i] = out[i] = 0;
G[i].clear();
}
dfn[0] = 1;
fa[0] = -1;
}
void add( LL x,LL y ){
G[x].push_back( y );
}
bool dfs(LL x){
inst[x] = 1;
for( LL i = 0;i < G[x].size();i++ ){
LL y = G[x][i];
if( dfn[y] && !inst[y] ){ // 排除后向边和横向边（其实后向边也不可以
return false; 存在，请读者自己思考其中原因）
}
if( dfn[y] && dfn[y] < dfn[x] ){
for( LL cur = x;cur != y;cur = fa[cur] ){ // 找到圈，将除了圈的起始点以外所有的
if( c[cur] >= 1 ){ 点全部做标记，如果一个点被标记了两
return false; 次，return false。
}else{
c[cur] += 1;
}
}
}else if(!dfn[y]){
fa[y] = x;
dfn[y] = dfn[x] + 1;
if( !dfs(y) ) return false;
}
}
inst[x] = 0;
return true;
}
bool judge( ){
for( LL i = 0; i < n; i++ ){
if( in[i] != out[i] ) return false; // 判定欧拉回路
}
if(!dfs(0)) return false;
for( LL i = 0;i < n;i++ ){
if( !dfn[i] ) return false; // 排除多个连通分量的情况
}
return true;
}
int main()
{
//freopen( "123.txt","r",stdin );
LL T,x,y;
scanf("%lld",&T);
while( T-- ){
scanf("%lld%lld",&n,&m);
init();
for(LL i = 0;i < m;i++){
scanf("%lld%lld",&x,&y);
in[y]++;
out[x]++;
add( x,y );
}
if( judge() ){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}二 无向cactus 图
无向cactus图与有向最大的区别在于无向图的每个点至多在一个圈上（当然可以存在一个点不属于任何一个圈）。无向catus图也可以理解为由若干个圈组成，且圈与圈两两之间最多有一个交点。
uvalive 3514
思路：本题不光要求判定是否为cactus图，还要求求出每个圈节点个数。于是我们模仿刚才的方法二
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e4+5;
vector<int> G[maxn];
int n,m,K;
int cylcnt;
int c[maxn], dfn[maxn],f[maxn];
int ans[maxn], cycle[maxn];
void add_edge(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
void init(){
cylcnt=0;
for(int i=1;i<=n;i++) {
G[i].clear();
c[i] = 0;
dfn[i] = 0;
}
memset( ans,0,sizeof(ans) );
}
void dfs(int x,int fa){
for( int i = 0;i < G[x].size();i++ ){
int y = G[x][i];
if( y == fa ) continue;
if( !dfn[y] ){
f[y] = x;
dfn[y] = dfn[x] + 1;
dfs( y,x );
}else if( dfn[y] < dfn[x] ){ // 找到一个圈
int cnt = 0;
for( int cur = x;cur != y;cur = f[cur] ){
c[cur]++;
cnt++;
}
cycle[cylcnt++] = cnt+2;
}
}
}
void get_ans(){
int len=0;
ans[len]=1;
for(int i=0;i<cylcnt;i++){
for(int j=0;j<=len;j++)
ans[j]*=cycle[i];
for(int j=0;j<=len;j++){
ans[j+1]+=ans[j]/10;
ans[j]%=10;
}
while(ans[len+1]){
ans[len+2]+=ans[len+1]/10;
ans[++len]%=10;
}
}
for(int i=len;i>=0;i--)
printf("%d",ans[i]);
puts(""); //输出一个'\0'
}
int main(){
//freopen( "123.txt","r",stdin );
int u, v;
int cas=0;
while(~scanf("%d%d",&n, &m)){
init();
if(cas++!=0)
puts("");
for(int i=0;i<m;i++){
scanf("%d",&K);
scanf("%d",&u);
for(int i=1;i<K;i++){
scanf("%d",&v);
add_edge(u,v);
u=v;
}
}
dfn[1]=1;
dfs(1,-1);
bool flag = true;
for(int i=1;i<=n;i++)
if(dfn[i]==0||c[i]>1){
flag = false;
break;
}
if( !flag ){
puts("0");
continue;
}
get_ans();
}
return 0;
}
最后附上一篇论文，如果上面没看懂可以看看这一篇
类似资料：