仙人掌图的判定

Posted on   |   In

无向图上仙人掌图的判定

例题洛谷P4129

通过$tarjan$ 求出所有的点双分量

根据仙人掌图的性质 我们对于包含非树边的点双分量 判断是否是简单环即可(通过判环的点数是否等于边数)

注意仙人掌图的前提 图是联通的

然后注意这题 统计答案会很大 所以需要写高精度(黄大佬的高精板子真的快啊)

复杂度 $O(n+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// 仙人掌是指无向连通图中,每一条边最多出现在一个简单环上
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const int NM=1e6+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct Huge{
    static const int MAXN=10001;
    static const int BASE=10000;
    int Num[MAXN];
    int len;
    void init(const string &s){
        memset(Num,0,sizeof(Num));
        int rlen=s.size();
        len=0;
        int i;
        for (i=rlen-5;i>=0;i-=4){
            Num[len]=Num[len]*10+s[i+1]-'0';
            Num[len]=Num[len]*10+s[i+2]-'0';
            Num[len]=Num[len]*10+s[i+3]-'0';
            Num[len]=Num[len]*10+s[i+4]-'0';
            len++;
        }
        if (i<0) i+=4;
        for (int j=0;j<=i;j++)
            Num[len]=Num[len]*10+s[j]-'0';
        len++;
    }
    friend istream& operator>>(istream &i, Huge &v){
        string s;
        i>>s;
        v.init(s);
        return i;
    }
    friend ostream& operator<<(ostream &o, Huge &v){
        if (v.len==0 && v.Num[0]==0){
            o<<'0';
            return o;
        }
        o<<v.Num[v.len-1];
        for (int i=v.len-2;i>=0;i--)
            o<<setw(4)<<setfill('0')<<v.Num[i];
        return o;
    }
    void operator+=(const Huge &v)
    {
        int nlen=max(v.len,len);
        for (int i=0;i<nlen;i++){
            Num[i]+=v.Num[i];
            if (Num[i]>=BASE){
                Num[i]-=BASE;
                Num[i+1]++;
            }
        }
        if (Num[nlen]!=0) nlen++;
        len=nlen;
        //return (*this);
    }
    void operator-=(const Huge &v){
        int nlen=max(v.len,len);
        for (int i=0;i<nlen;i++){
            Num[i]-=v.Num[i];
            if (Num[i]<0){
                Num[i]+=BASE;
                Num[i+1]--;
            }
        }
        while (Num[nlen]==0 && nlen>=0) nlen--;
        len=nlen+1;
        //return (*this);
    }
    void operator*=(const Huge &v){
        Huge c;
        c.init("0");
        for (int i=0;i<len;i++)
            for (int j=0;j<v.len;j++){
                c.Num[i+j]+=Num[i]*v.Num[j];
                if (c.Num[i+j]>=BASE){
                    c.Num[i+j+1]+=c.Num[i+j]/BASE;
                    c.Num[i+j]%=BASE;
                }
            }
        c.len=len+v.len;
        while (c.Num[c.len]==0 && c.len>=0) c.len--;
        len=c.len+1;
        for (int i=0;i<len;i++) Num[i]=c.Num[i];
        //return (*this);
    }
    bool operator<(const Huge &v){
        if (len!=v.len) return len<v.len;
        for (int i=len-1;i>=0;i--)
            if (Num[i]!=v.Num[i]) return Num[i]<v.Num[i];
        return 0;
    }
};
int low[MAXN],dfn[MAXN],tarjan_bcc[MAXN];
bool vis[MAXN],pis[NM];
int Num[NM];
vector<int>vec[NM];
int st[NM],tot,cnt,num;
typedef struct node{
    int x,y;
}node;
node d[NM];
Huge ans,ans1;
string trans(int x){
    string y;
    while(x){
	int t1=x%10;x-=t1;x/=10;
	y.push_back((char)(t1+'0'));
    }
    reverse(y.begin(),y.end());
    return y;
}
void tarjan_Bcc(int x,int pre){
    vis[x]=1;low[x]=dfn[x]=++cnt;
    link(x){
	if(vis[j->t]&&dfn[j->t]<dfn[x]&&j->t!=pre){
	    st[++tot]=j->v;pis[j->v]=1;
	    low[x]=min(low[x],dfn[j->t]);
	}
	else if(!vis[j->t]){
	    st[++tot]=j->v;
	    tarjan_Bcc(j->t,x);
	    low[x]=min(low[x],low[j->t]);
	    if(low[j->t]>=dfn[x]){
		num++;vec[num].clear();
		while(1){
		    int y=st[tot--];
		    if(pis[y])Num[num]++;
		    if(tarjan_bcc[d[y].x]!=num){
			vec[num].pb(d[y].x);
			tarjan_bcc[d[y].x]=num;
		    }
		    if(tarjan_bcc[d[y].y]!=num){
			vec[num].pb(d[y].y);
			tarjan_bcc[d[y].y]=num;
		    }
		    if(j->v==y)break;
		}
		if(Num[num]==1)ans1.init(trans(vec[num].size()+1)),ans*=ans1;
	    }
	}
    }
}
int n,m;
int main(){
    int cnt1=0;
    n=read();m=read();
    ans.init(trans(1));
    inc(i,1,m){
	int k=read();int last=read();
	inc(j,2,k){
	    int x=read();cnt1++;
	    d[cnt1].x=x;d[cnt1].y=last;
	    add(x,last,cnt1);
	    add(last,x,cnt1);
	    last=x;
	}
    }
    int cnt2=0;
    inc(i,1,n)if(!vis[i])tarjan_Bcc(i,0),cnt2++;
    if(cnt2>1){printf("0\n");return 0;}
    inc(i,1,num)if(Num[i]>1){printf("0\n");return 0;}
    cout<<ans<<'\n';
    return 0;
}

有向图上仙人掌图的判断

例题hdu3594

参考博客仙人掌

首先我们通过$tarjan$ 判断图的强连通性

然后构造$dfs$树 通过分析 如果包含交叉边(两个端点不在同一个子树中) 前向边(出点是入点的祖先)则一定不满足仙人掌图

然后类似于树上差分的做法 判断一个边是否被多次覆盖即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// 仙人掌是指无向连通图中,每一条边最多出现在一个简单环上
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const int NM=1e6+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int dfn[MAXN],low[MAXN],tot;
bool kis[MAXN],Kis[MAXN];
stack<int>s;
int Num;
void tarjan_scc(int x){
    dfn[x]=low[x]=++tot;
    s.push(x);kis[x]=1;
    link(x){
	if(!dfn[j->t]){
	    tarjan_scc(j->t);
	    low[x]=min(low[x],low[j->t]);
	}
	else if(kis[j->t]){
	    low[x]=min(low[x],dfn[j->t]);
	}
    }
    if(low[x]==dfn[x]){
	Num++;Kis[x]=1;
	while(1){
	    int y=s.top();
	    if(y!=x)s.pop(),kis[y]=0,Kis[y]=1;
	    else break;
	}
    }
}
typedef struct node{
    int x,y;
}node;
node d[MAXN];
int fa[MAXN],dep[MAXN],num[MAXN],son[MAXN];
bool vis[MAXN],pis[NM];
vector<int>vec[MAXN];
int cnt,p[MAXN];
void dfs(int x,int pre,int deep){
    fa[x]=pre;dep[x]=deep+1;num[x]=1;vis[x]=1;
    p[x]=++cnt;
    link(x){
	if(vis[j->t])continue;
	pis[j->v]=1;vec[x].pb(j->t);
	dfs(j->t,x,deep+1);
	num[x]+=num[j->t];
	if(son[x]==-1||num[son[x]]<num[j->t])son[x]=j->t;
    }
}
int tp[MAXN];
void _dfs(int x,int td){
    tp[x]=td;
    if(son[x]!=-1)_dfs(son[x],td);
    for(int i=0;i<vec[x].size();i++)if(vec[x][i]!=fa[x]&&vec[x][i]!=son[x])_dfs(vec[x][i],vec[x][i]);
}
int Lca(int x,int y){
    int xx=tp[x];int yy=tp[y];
    while(xx!=yy){
	if(dep[xx]<dep[yy])swap(xx,yy),swap(x,y);
	x=fa[xx];xx=tp[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int sum[MAXN];
void __dfs(int x,int pre){
    for(int i=0;i<vec[x].size();i++){
	if(vec[x][i]==pre)continue;
	__dfs(vec[x][i],x);
	sum[x]+=sum[vec[x][i]];
    }
}
int main(){
    int _=read();
    while(_--){
	int n=read();cnt=0;
	memset(h,0,sizeof(h));o=e;
	memset(Kis,0,sizeof(Kis));
	memset(dfn,0,sizeof(dfn));
	inc(i,1,n)sum[i]=vis[i]=0,vec[i].clear(),son[i]=-1;
	Num=tot=0;
	int x,y;int cnt1=0;
	while(~scanf("%d%d",&x,&y)){
	    if(!x&&!y)break;
	    ++cnt1;d[cnt1].x=x+1;d[cnt1].y=y+1;
	    add(x+1,y+1,cnt1);
	}
	inc(i,1,n)if(!dfn[i])tarjan_scc(i);
	inc(i,1,cnt1)pis[i]=0;
	dfs(1,0,0);
	_dfs(1,1);
	bool flag=0;
	inc(i,1,cnt1){
	    if(pis[i])continue;
	    int lca=Lca(d[i].x,d[i].y);
	    if(lca==d[i].x){flag=1;break;}
	    if(lca!=d[i].y){flag=1;break;}
	    sum[d[i].x]++;sum[d[i].y]--;
	}
	inc(i,1,n)if(!Kis[i]){flag=1;break;}
	if(Num>=2){flag=1;break;}
	if(flag){printf("NO\n");continue;}
	__dfs(1,0);
	inc(i,2,n)if(sum[i]>1){printf("NO\n");flag=1;break;}
	if(!flag)printf("YES\n");
    }
    return 0;
}