[题目链接]

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 ; }

最新文章

  1. Objective-C 源码初探 __attribute__
  2. mysql在linux下修改存储路径
  3. Python之路【第十二篇续】jQuery案例详解
  4. Hadoop之Storm命令
  5. windows 下mysql每日定时备份的几种方法
  6. C#WebBrowser控件使用教程与技巧收集--苏飞收集
  7. rspec的一些常见用法
  8. HDU 3567 Eight II BFS预处理
  9. javaweb学习总结(三十四)——使用JDBC处理MySQL大数据
  10. CentOS 6下配置本地用户访问vsftpd并赋予写权限
  11. A function to help graphical model checks of lm and ANOVA(转)
  12. Rabbitmq集群高可用
  13. [LeetCode] Champagne Tower 香槟塔
  14. 3.JAVA基础复习——JAVA中的类与对象
  15. Cartographer源码阅读(7):轨迹推算和位姿推算的原理
  16. MySQL5.7 Group Replication (MGR)--Mysql的组复制之多主模式
  17. 【转】使用notepad运行python
  18. idea 关闭自动保存,未保存星号提醒, springboot + freemarker 热部署
  19. Spring boot 配置文件 加载顺序
  20. ABP之应用服务(2)

热门文章

  1. JS——百度背景图
  2. CSS——float
  3. Windows2008 Server 常规设置及基本安全策略
  4. 关于Qt 报QDomDocument: No such file or directory错误解决办法
  5. Mirror用法
  6. 数组的复制 --System.arraycopy()
  7. HDU 3152 Obstacle Course(优先队列,广搜)
  8. codevs 3385 拯救Oier(一) Save Oier—first
  9. 谈一谈Dijkstra
  10. clock()函数的使用