当前位置:网站首页>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);
}
}
边栏推荐
- C language: reverse character order
- The maximum validity period of an SSL certificate is 13 months. Is it necessary to apply for multiple years at a time?
- (四)BP神经网络预测(上)
- 【Template】Tree Chain Segmentation P3384
- imageio读取.exr报错 ValueError: Could not find a backend to open `xxx.exr‘ with iomode `r`
- es6 基础知识详解 变量 字符串 解构赋值 函数 对象 从入门到精通
- RK3568商显版开源鸿蒙板卡产品解决方案
- 重要消息丨.NET Core 3.1 将于今年12月13日结束支持
- Anaconda 使用代理
- 【转载】Deep Learning(深度学习)学习笔记整理
猜你喜欢
随机推荐
Kotlin Coroutines - Exception Handling
unity第一课
解决pycharm每次新建项目都要重新pip安装一些第三方库等问题
MUV LUV EXTRA 2019CCPC秦皇岛站J题 KMP
差分约束-图论
2017 G icpc shenyang Infinite Fraction Path BFS + pruning
高德地图JS - 已知经纬度来获取街道、城市、详细地址等信息
Four departments including the Ministry of Industry and Information Technology promote green smart home products to the countryside
Change Jupyter Notebook default open directory
sklearn数据预处理
XILINX K7 FPGA+RK3399 PCIE驱动调试
排序第三节——交换排序(冒泡排序+快速排序+快排的优化)(5个视频讲解)
RestFul,会话技术,Fiddler
Pytorch中 nn.BatchNorm2d() 归一化操作
记录一次客户的APP数据库版本号升级失败的情况
CoCube传感器MPU6050笔记
接口测试概念
74HC595 chip pin description
Anaconda 使用代理
【Reprint】Deep Learning (deep learning) study notes arrangement