首页 > 其他分享 >CF118E Bertown roads

CF118E Bertown roads

时间:2024-04-27 09:00:42浏览次数:30  
标签:tarjan CF118E int Bertown roads include 节点 define

CF118E Bertown roads

结论+tarjan/dfs tree

首先图中有桥肯定无解,那么考虑不存在桥的时候怎么构造一种解。

现在图是个边双,有什么算法?tarjan。从 tarjan 入手,遍历过程将图分为了树边和返祖边(无向图中不存在横叉边和前向边,可以模拟 dfs 过程理解),那么我们可以让树边由父亲连向儿子,这样根节点就能够到达所有节点;同时可以发现,所有节点都可以到达根,因为图是边双,也就是任意节点的子树内都存在一条返祖边可以跳到该节点的祖先(如果没有这样的边,那么就是割点了)。

所以跑一遍 tarjan/dfs tree,同时定向即可。

复杂度 \(O(n)\)。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <bitset>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int n, m, cnt = 1, idx, tot, num;
int h[N], dfn[N], low[N];
pii ans[N];
struct node {
	int to, nxt;
} e[N << 1];
void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = h[u];
	h[u] = cnt;
}
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tot;
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(!dfn[v]) {
			tarjan(v, i);
			ans[++num] = {u, v};
			low[u] = std::min(low[u], low[v]);
		} else if(i != (fa ^ 1)) {
			low[u] = std::min(low[u], dfn[v]); 
			if(dfn[v] < dfn[u]) ans[++num] = {u, v};
		}
	}
	if(low[u] == dfn[u]) idx++;
}
int dec[N << 1];
void Solve() {
	std::cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v;
		std::cin >> u >> v;
		add(u, v), add(v, u);
	}
	for(int i = 1; i <= n; i++) {
		if(!dfn[i]) tarjan(i, 0);
	}
	if(idx != 1) {
		std::cout << "0\n";
		return;
	}
	for(int i = 1; i <= m; i++) {
		std::cout << ans[i].fi << " " << ans[i].se << "\n";
	}
}	
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}

标签:tarjan,CF118E,int,Bertown,roads,include,节点,define
From: https://www.cnblogs.com/FireRaku/p/18161253

相关文章

  • CF1149D Abandoning Roads 题解
    Description一张\(n\)个点\(m\)条边的无向图,只有\(a,b\)两种边权(\(a<b\)),对于每个\(i\),求图中所有的最小生成树中,从\(1\)到\(i\)距离的最小值。\(2\leqn\leq70,n-1\leqm\leq200,1\leqa<b\leq10^7\)。Solution先考虑一个最小生成树是什么样的形态,显然保留边权......
  • Codeforces 264E Roadside Trees
    首先考虑时间增长的问题,设第\(i\)棵树的种植时间为\(t_i\)。那么第\(x\)棵树比第\(y\)棵树高就是\(h_x+(t_y-t_x)>h_y\),也就是\(h_x-t_x>h_y-t_y\)。所以可以直接用\(h_i-t_i\)当作第\(i\)棵树的高度,即\(h'_i\leftarrowh_i-t_i\)。对于增加,考虑......
  • 24/02/04 CF567E President and Roads
    题目描述Berlandhas$n$cities,thecapitalislocatedincity$s$,andthehistorichometownofthePresidentisincity$t$($s≠t$).Thecitiesareconnectedbyone-wayroads,thetraveltimeforeachoftheroadisapositiveinteger.Once......
  • 特斯拉开源 Roadster 文件随便用;微软 Copilot AI 技术开放或不对大陆开放丨 RTE 开发
       开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑......
  • 特斯拉开源 Roadster 文件随便用;微软 Copilot AI 技术开放或不对大陆开放丨 RTE 开发
      开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个人观点,......
  • CF773D Perishable Roads
    题目描述:有一个\(n\)个点的图,对于每两个点\((i,j)\)之间都有一条长度为\(w_{i,j}\)的无向边。给你一个点\(t\),你需要构造一棵以\(t\)为根的生成树,使得\(\sum\limits_{i=1}^{n}s(i,t)\)尽量小。\(s(i,t)\)为\(i\rightarrowt\)的树上路径上的最小权值。你需要对于......
  • CF543B Destroying Roads
    好经典的题,因为暑假前集训做过类似的思想的题所以知道怎么处理这题由于要求最多的删去的边数,则等价于求最少保留几条边,很显然留下的边一定是最短路上的但问题是如果两条路不相交的话很简单,可事实是两条路径可以重叠一些部分,这些边用了两次可能可以使答案变优关于这种图上两条路......
  • 题解:CF118E
    Tarjan思路先来看一下题目给出的无解的这个样例。不难发现,导致无解的两条边就是\(6-7\)和\(2-4\)这两个桥。所以这个题就转换成了求桥,如果存在桥就是无解。代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5,M=3e5+5;inlineintread();intn,......
  • CF1149D Abandoning Roads
    首先\(a\)边可以随便选。显然,若某条\(b\)边的两端位于同一\(a\)连通块,一定不会被我们考虑。剩下的\(b\)边一定会将两个\(a\)连通块相连。那么此时我们对于\(b\)边的约束是,位于一个环上的\(b\)边不能同时存在图中,即,我们的路径不能从当前连通块出发,经过至少一条\(b......
  • CodeForces 1149D Abandoning Roads
    洛谷传送门CF传送门考虑一条\(1\toi\)的路径是否在最小生成树上。称边权为\(a\)的边为轻边,边权为\(b\)的边为重边。轻边若不成环则一定在最小生成树上,因此先把轻边合并,这样形成了若干连通块。那么如果两点在一个连通块,它们只能通过轻边互达。同时,因为是树上路径,所......