首页 > 其他分享 >Living-Dream 系列笔记 第86期

Living-Dream 系列笔记 第86期

时间：2024-11-16 20:19:12浏览次数：1  
标签：Living cur nxt int 86 dfn low include Dream

边双连通分量

概念：若在无向图 \(G\) 中，存在一个极大子图 \(G'\)，使得 \(G'\) 中没有割边，则称 \(G'\) 为 \(G\) 的一个边双连通分量，记作 \(\texttt{E-DCC}\)。

使用场景：将无向图转化为一棵树（即无向图上的缩点）。

求解步骤：确定割边，再遍历所有点且不经过割边，那么能联通的点都是即在同一个 \(\texttt{E-DCC}\) 中。

T103489

板子。

code 
#include<bits/stdc++.h>
using namespace std;

const int N=3e5+5;
int n,m,cnt,id;
int dfn[N],low[N],dcc[N];
bool bridge[N];
struct NODE{
	int v,i;
};
vector<NODE> G[N];

void tarjan(int cur,int edg){
	dfn[cur]=low[cur]=++cnt;
	for(auto nxt:G[cur]){
		if(!dfn[nxt.v]){
			tarjan(nxt.v,nxt.i);
			low[cur]=min(low[cur],low[nxt.v]);
			if(low[nxt.v]>dfn[cur])
				bridge[nxt.i]=1;
		}
		else if(nxt.i!=edg){
			low[cur]=min(low[cur],dfn[nxt.v]);
		}
	}
}
void dfs(int cur){
	dcc[cur]=id;
	for(auto nxt:G[cur]){
		if(dcc[nxt.v]||bridge[nxt.i])
			continue;
		dfs(nxt.v);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		G[u].push_back({v,i});
		G[v].push_back({u,i}); 
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,0);
	for(int i=1;i<=n;i++)
		if(!dcc[i])
			++id,dfs(i);
	cout<<id; 
	return 0;
}

POJ3352

结论题。

考虑缩点，形成的树上就都是割边了。

现在要连边成环从而消去割边带来的影响。

要求连边最少，也就是每次消去的割边要尽可能多。

怎么消去的最多？这等价于问树上哪条路径最长。

那显然就是连直径的两个端点。

而众所周知，直径的端点只有可能是度数为 \(1\) 的节点。

即叶子节点 + 度数为 \(1\) 的根（根在度数 \(>1\) 时显然不会比叶子节点更优）。

于是寻找度数为 \(1\) 的根两两相连即可，有落单的则还需连一次。

令度数为 \(1\) 的点有 \(x\) 个，这说明答案即为 \(\lceil \frac{x}{2} \rceil\)。

code 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int N=1e3+5;
int n,m,cnt,id;
int dfn[N],low[N],dcc[N],dg[N];
bool bridge[N],ok[N][N];
struct NODE{
	int v,i;
};
vector<NODE> G[N];
struct EDGE{
	int u,v;
}e[N];

void tarjan(int cur,int edg){
	dfn[cur]=low[cur]=++cnt;
	for(int nxt=0;nxt<G[cur].size();nxt++){
		if(!dfn[G[cur][nxt].v]){
			tarjan(G[cur][nxt].v,G[cur][nxt].i);
			low[cur]=min(low[cur],low[G[cur][nxt].v]);
			if(low[G[cur][nxt].v]>dfn[cur])
				bridge[G[cur][nxt].i]=1;
		}
		else if(G[cur][nxt].i!=edg){
			low[cur]=min(low[cur],dfn[G[cur][nxt].v]);
		}
	}
}
void dfs(int cur){
	dcc[cur]=id;
	for(int nxt=0;nxt<G[cur].size();nxt++){
		if(dcc[G[cur][nxt].v]||bridge[G[cur][nxt].i])
			continue;
		dfs(G[cur][nxt].v);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		e[i]={u,v};
		G[u].push_back({v,i});
		G[v].push_back({u,i}); 
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,0);
	for(int i=1;i<=n;i++)
		if(!dcc[i])
			++id,dfs(i);
	for(int i=1;i<=m;i++){
		if(bridge[i]){
			dg[dcc[e[i].u]]++;
			dg[dcc[e[i].v]]++;
		}
	}
	int ans=0;
	for(int i=1;i<=id;i++)
		if(dg[i]==1)
			ans++;
	cout<<(ans+1)/2;
	return 0;
}

总结：做题时注意题面信息的转化。

POJ3694

如果只有一次询问，那么答案就是两个点所在的 \(\texttt{E-DCC}\) 在缩点后的树上的简单路径长度。

考虑多组询问，其实没什么区别，就是可能有重复的边，

于是我们不能直接求了，只能一步步往 LCA 跳，

但是这个时候再去走这些重复边就是浪费，于是我们用并查集优化一下即可。

思维难度很低对吧，但是我这个唐诗儿调了一上午 /fn/fn/fn

code 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int N=1e5+5,M=2e5+5;
int n,m,q;
int cnt,id,ans,tot,test;
int dfn[N],low[N],dcc[N];
int dp[N][18],dep[N],fa[N];
bool bridge[M<<1];
struct NODE{
	int v,i;
};
vector<NODE> G[N];
struct EDGE{
	int u,v;
}e[M];
vector<int> T[N];

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');
    return;
}
void tarjan(int cur,int edg){
	dfn[cur]=low[cur]=++cnt;
	for(int nxt=0;nxt<G[cur].size();nxt++){
		if(!dfn[G[cur][nxt].v]){
			tarjan(G[cur][nxt].v,G[cur][nxt].i);
			low[cur]=min(low[cur],low[G[cur][nxt].v]);
			if(low[G[cur][nxt].v]>dfn[cur])
				bridge[G[cur][nxt].i]=1;
		}
		else if(G[cur][nxt].i!=edg){
			low[cur]=min(low[cur],dfn[G[cur][nxt].v]);
		}
	}
}
void dfs(int cur){
	dcc[cur]=id;
	for(int nxt=0;nxt<G[cur].size();nxt++){
		if(dcc[G[cur][nxt].v]||bridge[G[cur][nxt].i])
			continue;
		dfs(G[cur][nxt].v);
	}
}
void init(){
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(dcc,0,sizeof dcc);
	memset(bridge,0,sizeof bridge);
	cnt=id=0;
	for(int i=1;i<=n;i++)
		G[i].clear();
}
void Init(){
	for(int i=1;i<=id;i++)
		T[i].clear(),fa[i]=i;
}
void init_lca(int cur,int father){
	dep[cur]=dep[father]+1;
	dp[cur][0]=father;
	for(int i=1;(1<<i)<=dep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(int nxt=0;nxt<T[cur].size();nxt++){
		if(T[cur][nxt]==father)
			continue;
		init_lca(T[cur][nxt],cur);
	}
}
int get_lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=17;i>=0;i--)
		if(dep[dp[x][i]]>=dep[y])
			x=dp[x][i];
	if(x==y)
		return x;
	for(int i=17;i>=0;i--)
		if(dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}
int fnd(int x){
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void jump(int x,int ed){
	x=fnd(x);
	while(dep[x]>dep[ed]){
		fa[x]=dp[x][0];
		ans--;
		x=fnd(x);
	}
} 

int main(){
	while(1){
		n=read(),m=read();
		if(n==0&&m==0)
			break;
		cout<<"Case "<<++test<<":\n";
		init();
		for(int i=1,u,v;i<=m;i++){
			u=read(),v=read();
			e[i]={u,v};
			G[u].push_back({v,i});
			G[v].push_back({u,i});
		}
		for(int i=1;i<=n;i++)
			if(!dfn[i])
				tarjan(i,0);
		for(int i=1;i<=n;i++)
			if(!dcc[i])
				++id,dfs(i);
		Init();
		for(int i=1;i<=m;i++){
			if(bridge[i]){
				T[dcc[e[i].u]].push_back(dcc[e[i].v]);
				T[dcc[e[i].v]].push_back(dcc[e[i].u]);
			}
		}
		q=read();
		init_lca(1,0);
		ans=id-1;
		while(q--){
			int a,b;
			cin>>a>>b;
			a=dcc[a],b=dcc[b];
			int lca=get_lca(a,b);
			jump(a,lca),jump(b,lca);
			write(ans);
			putchar('\n');
		}
		putchar('\n');
	}
	return 0;
}

总结：做题从简单情况入手。

CF231E

简单题，10 min 一遍过。tj。

标签：Living,cur,nxt,int,86,dfn,low,include,Dream
From： https://www.cnblogs.com/XOF-0-0/p/18549765

相关文章

  • 打卡信奥刷题（239）用C++工具信奥P1866 [普及组/提高] 编号
    编号题目描述太郎有NNN只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好，每个兔子i......
  • Codeforces Round 986 (Div. 2)
    AB没什么好说的。C把我卡了。dp非常明显，最开始我想的是单向做，\(f[i][0/1]\)表示前\(i\)块蛋糕已经分出去了，01表示Alice是否拿过了，此时分给了几个人。尝试写写转移就知道为什么寄了。状态不够，没法表示答案。就算转移到了最后也没法得出我们需要的答案。可以发现，这个dp不好做的......
  • 【题解】洛谷P11186： 三目运算
    不好玩！！！这是个树形结构，直接暴力模拟，但过不去，但是需要发现答案是个区间，我们对字符串处理时记录最大值最小值，然后到叶子节点时我们将此时的区间存起来，查询时直接二分查询这个数对于的区间就可以了。总结：不好玩！！！#include<bits/stdc++.h>usingnamespacestd;#definelllonglon......
  • P8863 「KDOI-03」构造数组
    P8863「KDOI-03」构造数组cplusoj：SS241113D.构造数组(array)题意给你一个长度为\(n\le5000\)的数组\(\{b\}\)，满足\(\sumb\le30000\)。每次操作你可以选择两个下标\(i,j,i\neqj\)，将\(b_i,b_j\)减\(1\)，问有多少种操作方式使得\(b\)变成全部是\(0\)。思路看......
  • 部署zabbix遇到问题: cannot find a valid baseurl for repo：centos-sclo-rh/x86 64 怎
    安装Zabbix前端包，提示cannotfind avalidbaseurlforrepo：centos-sclo-rh/x8664安装zabbix前端包#yuminstallzabbix-web-mysql-sclzabbix-apache-conf-scl解决办法：原因是：CentOS7的SCL源在2024年6月30日停止维护了。 1.将之前的源进行备份cd/etc/yum.repos.d......
  • P8868 [NOIP2022] 比赛（线段树维护区间历史和）
    题意给定排列\(a,b\)，\(q\)次询问\(l,r\)，你需要求出\(\sum_{l\lel'\ler'\ler}(\max_{i=l'}^{r'}a_i)(\max_{i=l'}^{r'}b_i)\)对\(2^{64}\)取模的值。\(n,q\le2.5\times10^5\)分析根据经典套路，按\(r\)扫描线，维护两个单调栈，那么加入一个数就相当于进行若干段区......
  • P8680 [蓝桥杯 2019 省 B] 特别数的和 java
    题目描述小明对数位中含有 22、00、11、99 的数字很感兴趣（不包括前导 00），在 11 到 4040 中这样的数包括 11、22、99、1010 至 3232、3939 和 4040，共 2828 个，他们的和是 574574。请问，在 11 到 nn 中，所有这样的数的和是多少？输入格式输入一行包含一个整数 ......
  • 【题解】洛谷P7286：「EZEC-5」人赢
    P7286「EZEC-5」人赢可以想到对于每个数要找到比他大的数中下标最大的数，我们按照数的大小排序，我们维护原序列的一个指针，对于每个数如果比指针大那么就左移指针，可以思考下为什么：指针上的数比现在这个数要小那比后面的数都小，于是我们左移指针直到大于这个数，可以发现我们也在一直......
  • MUR860AC-ASEMI快恢复二极管MUR860AC
    编辑：llMUR860AC-ASEMI快恢复二极管MUR860AC型号：MUR860AC品牌：ASEMI封装：TO-220AC特性：插件二极管正向电流：8A反向耐压：600V恢复时间：35ns引脚数量：2芯片个数：1芯片尺寸：MIL浪涌电流：125A漏电流：10ua工作温度：-55℃~150℃包装方式：500/盘；5000/箱备受欢迎的MUR860AC-ASEMI快恢复......
  • 【最新原创毕设】基于移动端的助农电商系统+08655（免费领源码）可做计算机毕业设计JAVA、
    基于移动端的助农电商系统的设计与实现摘要近年来，电子商务的快速发展引起了行业和学术界的高度关注。基于移动端的助农电商系统旨在为用户提供一个简单、高效、便捷的农产品购物体验，它不仅要求用户清晰地查看所需信息，而且还要求界面设计精美，使得功能与页面完美融合，从而提升......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99