Codeforces 160D Edges in MST tarjan找桥
2024-09-21 12:44:24
在用克鲁斯卡尔求MST的时候, 每个权值的边分为一类, 然后将每类的图建出来, 那些桥就是必须有的, 不是桥就不是必须有。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); struct Edge {
int a, b, id, tmp1, tmp2;
}; int n, m, fa[N], ans[N];
bool brige[N];
int dfn[N], low[N], idx;
vector<Edge> vc[N];
vector<PII> G[N]; int getRoot(int x) {
return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
} void tarjan(int u, int id) {
dfn[u] = low[u] = ++idx;
for(auto& e : G[u]) {
if(e.se == id) continue;
if(!dfn[e.fi]) {
tarjan(e.fi, e.se);
low[u] = min(low[u], low[e.fi]);
if(dfn[u] < low[e.fi]) brige[e.se] = true;
} else low[u] = min(low[u], dfn[e.fi]);
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i <= m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
vc[w].push_back(Edge{a, b, i, , });
}
for(int i = ; i <= ; i++) {
if(!SZ(vc[i])) continue;
idx = ;
for(auto& e : vc[i]) {
e.tmp1 = getRoot(e.a);
e.tmp2 = getRoot(e.b);
if(e.tmp1 > e.tmp2) swap(e.tmp1, e.tmp2);
}
for(auto& e : vc[i]) {
if(e.tmp1 == e.tmp2) {
ans[e.id] = ;
} else {
G[e.tmp1].clear();
G[e.tmp2].clear();
dfn[e.tmp1] = dfn[e.tmp2] = ;
}
}
for(auto& e : vc[i]) {
if(e.tmp1 != e.tmp2) {
G[e.tmp1].push_back(mk(e.tmp2, e.id));
G[e.tmp2].push_back(mk(e.tmp1, e.id));
}
}
for(auto& e : vc[i]) {
if(e.tmp1 != e.tmp2) {
if(!dfn[e.tmp1]) tarjan(e.tmp1, );
if(!dfn[e.tmp2]) tarjan(e.tmp2, );
}
}
for(auto& e : vc[i]) {
if(e.tmp1 != e.tmp2) {
if(brige[e.id]) ans[e.id] = ;
else ans[e.id] = ;
}
}
for(auto& e : vc[i]) {
int x = getRoot(e.a);
int y = getRoot(e.b);
if(x != y) fa[x] = y;
}
}
for(int i = ; i <= m; i++) {
if(ans[i] == ) puts("any");
else if(ans[i] == ) puts("at least one");
else puts("none");
}
return ;
} /*
*/
最新文章
- [备忘] Automatically reset Windows Update components
- jupyter nb + scite 混合搭建成我的最爱IDE
- IOS TableView 去除点击后产生的灰色背景
- iOS开发如何学习前端
- Spring Remoting: HTTP Invoker--转
- java post请求
- 巴科斯范式和sql语言
- 苹果推送APNS自己总结
- RedHat安装VMwareTools出现解压压缩包时无法打开文件的现象
- skinned mesh 蜘蛛样
- ISO 9141-2 and ISO 14230-2 INITIALIZATION and DATA TRANSFER
- ABAP程序执行效率和优化 ABAP Performance Examples
- Android Paint和Color类
- Linux Kernel 排程機制介紹
- 浩哥解析MyBatis源码(二)——Environment环境
- 《Head First Java》读书笔记(1) - Java语言基础
- linux虚拟机 在install yum时提示无法获得锁 var/lib/dekg/lock时该如何解决?
- 系统架构-设计模式(适配器、观察者、代理、抽象工厂等)及架构模式(C/S、B/S、分布式、SOA、SaaS)(干货)
- JSON.stringify转化报错
- Java IO的一些列子