当前位置:网站首页>Forest Program DFS + tanjar cactus
Forest Program DFS + tanjar cactus
2022-08-09 07:40:00 【swust_fang】
题目链接 CCPC2019 F题.
题意:Give a cactus tree,Let you find the number of sides of each small ring,It can be solved with fast powers.
思路:第一反应是tanjar乱搞,Take the dots out of each ring,Similar to the method of shrinking points.But suddenly feltdfs能做,Because of the special nature of cactus,That is, there will be no more than one branch on a ring.
So first we start from any point,dfsGo down to record depth and mark,When we reach a point marked off and the depth is less than the current point,Prove that we just walked a circle,Then the depth difference between the two points+1is the number of sides of the ring,What if the depth of the mark is greater than the depth of the current point,In fact, this is the ring we have dealt with before,Just skip it,就这样就完了.
dfs代码:
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=998244353;
const int maxn=3e5+5;
const int maxm=1e6+5;
struct node
{
int to,p;
}edge[maxm];
int head[maxn],sign;
int vis[maxn];
int n,m;
ll res;
ll qmod(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
ll qqmod(ll a,ll b)
{
ll ans=qmod(a,b);
ans=(ans-1+mod)%mod;
return ans;
}
void init()
{
for(int i=0;i<=n;i++) head[i]=-1,vis[i]=0;
sign=0;
}
void add(int u,int v)
{
edge[sign]=node{v,head[u]};
head[u]=sign++;
}
void dfs(int u,int cnt)
{
vis[u]=cnt;
for(int i=head[u];~i;i=edge[i].p)
{
int v=edge[i].to;
if(vis[v])
{
if(vis[u]-vis[v]>1)//Determine whether the parent node is gone
{
ll c=vis[u]-vis[v]+1;
res=res*qqmod(2,c)%mod;
m-=c;
}
}
else dfs(v,cnt+1);
}
}
int main()
{
int x,y;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(m==0)
{
puts("0");
continue;
}
init();
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
add(x,y),add(y,x);
}
res=1;
dfs(1,1);
res=res*qmod(2,m)%mod;
printf("%lld\n",res);
}
return 0;
}
然后就是tanjar的做法.
In fact, many people do this question with a double point, I don't think it is necessary,And what I write keeps timing out(-.-
问题在于tanjarTo find the Unicom component is actually to find a large ring,The second example is actually a large connected component
But the idea is probably the same,Also as a review.
当我们tanjar到一个点low[v]>=low[u]证明uA point is a cut point,The way we shrink the point is to put stackmedium until equal touAll points are taken out
Here is until equalsvJust take out all the points,然后+1is the block(The block description should be fine)The quantity is obtained,
Only the number of blocks is greater than 2Just a ring
代码是T的,不晓得为啥~(Hope you guys can help!
//#pragma comment (linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=998244353;
const int maxn=3e5+5;
const int maxm=1e6+5;
struct node
{
int to,p;
}edge[maxm];
int head[maxn],sign;
int n,m;
int Stack[maxn],low[maxn],dfn[maxn];
int num[maxn];
int top,t,cnt;
ll p[maxn],r[maxn];
ll res;
ll qmod(ll a,ll b)
{
if(r[b]) return r[b];
int c=b;
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return r[c]=ans;
}
ll qqmod(ll a,ll b)
{
if(p[b]) return p[b];
ll ans=qmod(a,b);
ans=(ans-1+mod)%mod;
return p[b]=ans;
}
void init()
{
t=top=cnt=sign=0;
for(int i=1;i<=n;i++)
{
low[i]=dfn[i]=0;
head[i]=-1;
}
}
void add(int u,int v)
{
edge[sign]=node{v,head[u]};
head[u]=sign++;
}
void tanjar(int u,int pre)
{
dfn[u]=low[u]=++t;
Stack[++top]=u;
for(int i=head[u];~i;i=edge[i].p)
{
int v=edge[i].to;
if(v==pre) continue;
if(!dfn[v])
{
tanjar(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
cnt++;
num[cnt]=0;
int x;
do{
x=Stack[top--];
num[cnt]++;
}while(x!=v);
num[cnt]++;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(m==0) {puts("0");continue;}
init();
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
add(x,y),add(y,x);
}
res=1;
for(int i=1;i<=n;i++)
if(!dfn[i]) tanjar(i,i);
for(int i=1;i<=cnt;i++)
if(num[cnt]>=3) res=res*qqmod(2,num[cnt])%mod,m-=num[cnt];
res=res*qmod(2,m)%mod;
printf("%lld\n",res);
}
}
边栏推荐
猜你喜欢
(二)、灰色预测模型(GM1,1)
DIMP:Learning Discriminative Model Prediction for Tracking 学习判别模型预测的跟踪
(四)BP神经网络预测(上)
pip安装更换镜像
排序第四节——归并排序(附有自己的视频讲解)
虚拟机网卡报错:Bringing up interface eth0: Error: No suitable device found: no device found for connection
Important news丨.NET Core 3.1 will end support on December 13 this year
Laravel文档阅读笔记-Rendering JSON(对JS变量进行赋值)
IDEA文件UTF-8格式控制台输出中文乱码
ImportError: cannot import name ‘imresize‘
随机推荐
SSM整合开发案例
sklearn数据预处理
imageio读取.exr报错 ValueError: Could not find a backend to open `xxx.exr‘ with iomode `r`
c语言位段
The maximum validity period of an SSL certificate is 13 months. Is it necessary to apply for multiple years at a time?
【机器学习】支持向量机(SVM)代码练习
String类创建的对象在JVM中的内存分配和equals与==的区别
SA-Siam:用于实时目标跟踪的双重连体网络A Twofold Siamese Network for Real-Time Object Tracking
Tkinter可以选择的颜色
unity第一课
failed (13: Permission denied) while connecting to upstream
原生JDBC操作数据库
XILINX K7 FPGA+RK3399 PCIE驱动调试
Invoker 2019CCPC Qinhuangdao Station I Question Simple DP
【机器学习】中国大学慕课《机器学习》课后习题(二)(回归)
数据库索引原理
Unity first lesson
SAP ALV 数据导出被截断的bug
Anaconda 使用代理
Laravel文档阅读笔记-Rendering JSON(对JS变量进行赋值)