[BZOJ 1718] Redundant Paths
2024-10-01 04:04:23
[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1718
[算法]
用Tarjan算法找出所有e-DCC(边-双联通分量),然后将这张图缩点,答案即为(缩点后的树的叶子节点的个数 + 1) / 2
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010
#define MAXM 10010 struct edge
{
int to,nxt;
} e[MAXM << ]; int i,n,m,cnt,s,timer,tot;
int head[MAXN],u[MAXM],v[MAXM],low[MAXN],dfn[MAXN],belong[MAXN],degree[MAXN];
bool is_bridge[MAXM << ]; inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline void tarjan(int u,int t)
{
int i,v;
dfn[u] = low[u] = ++timer;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!dfn[v])
{
tarjan(v,i);
low[u] = min(low[u],low[v]);
if (low[v] > dfn[u])
is_bridge[i] = is_bridge[i ^ ] = true;
} else if (i != (t ^ )) low[u] = min(low[u],dfn[v]);
}
}
inline void dfs(int u)
{
int i,v;
belong[u] = cnt;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!belong[v] && !is_bridge[i])
dfs(v);
}
} int main()
{ scanf("%d%d",&n,&m);
tot = ;
for (i = ; i <= m; i++)
{
scanf("%d%d",&u[i],&v[i]);
addedge(u[i],v[i]);
addedge(v[i],u[i]);
}
for (i = ; i <= n; i++)
{
if (!dfn[i])
tarjan(i,);
}
for (i = ; i <= n; i++)
{
if (!belong[i])
{
cnt++;
dfs(i);
}
}
for (i = ; i <= m; i++)
{
if (belong[u[i]] != belong[v[i]])
{
degree[belong[u[i]]]++;
degree[belong[v[i]]]++;
}
}
for (i = ; i <= cnt; i++) s += (degree[i] == );
printf("%d\n",(s + ) / ); return ; }
最新文章
- Objective-C 源码初探 __attribute__
- mysql在linux下修改存储路径
- Python之路【第十二篇续】jQuery案例详解
- Hadoop之Storm命令
- windows 下mysql每日定时备份的几种方法
- C#WebBrowser控件使用教程与技巧收集--苏飞收集
- rspec的一些常见用法
- HDU 3567 Eight II BFS预处理
- javaweb学习总结(三十四)——使用JDBC处理MySQL大数据
- CentOS 6下配置本地用户访问vsftpd并赋予写权限
- A function to help graphical model checks of lm and ANOVA(转)
- Rabbitmq集群高可用
- [LeetCode] Champagne Tower 香槟塔
- 3.JAVA基础复习——JAVA中的类与对象
- Cartographer源码阅读(7):轨迹推算和位姿推算的原理
- MySQL5.7 Group Replication (MGR)--Mysql的组复制之多主模式
- 【转】使用notepad运行python
- idea 关闭自动保存,未保存星号提醒, springboot + freemarker 热部署
- Spring boot 配置文件 加载顺序
- ABP之应用服务(2)