HDU - 3836 Equivalent Sets (强连通分量+DAG)
2024-10-19 04:23:07
题目大意:给出N个点,M条边。要求你加入最少的边,使得这个图变成强连通分量
解题思路:先找出全部的强连通分量和桥,将强连通分量缩点。桥作为连线,就形成了DAG了
这题被坑了。用了G++交的,结果一直RE,用C++一发就过了。。。
#include <cstdio>
#include <cstring>
#define N 20010
#define M 100010
#define min(a,b) ((a) > (b)?
(b): (a))
#define max(a,b) ((a) > (b)?
(a): (b))
struct Edge{
int from, to, next;
}E[M];
int head[N], sccno[N], pre[N], lowlink[N], stack[N], in[N], out[N];
int n, m, tot, dfs_clock, top, scc_cnt;
void AddEdge(int from, int to) {
E[tot].from = from;
E[tot].to = to;
E[tot].next = head[from];
head[from] = tot++;
}
void init() {
memset(head, -1, sizeof(head));
tot = 0;
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
AddEdge(u, v);
}
}
void dfs(int u) {
pre[u] = lowlink[u] = ++dfs_clock;
stack[++top] = u;
for (int i = head[u]; i != -1; i = E[i].next) {
int v = E[i].to;
if (!pre[v]) {
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if (!sccno[v]) {
lowlink[u] = min(lowlink[u], pre[v]);
}
}
int x;
if (pre[u] == lowlink[u]) {
scc_cnt++;
while (1) {
x = stack[top--];
sccno[x] = scc_cnt;
if (x == u)
break;
}
}
}
void solve() {
memset(sccno, 0, sizeof(sccno));
memset(pre, 0, sizeof(pre));
dfs_clock = top = scc_cnt = 0;
for (int i = 1; i <= n; i++)
if (!pre[i])
dfs(i);
if (scc_cnt <= 1) {
printf("0\n");
return ;
}
for (int i = 1; i <= scc_cnt; i++)
in[i] = out[i] = 1;
for (int i = 0; i < tot; i++) {
int u = E[i].from, v = E[i].to;
if (sccno[u] != sccno[v]) {
out[sccno[u]] = in[sccno[v]] = 0;
}
}
int a = 0, b = 0;
for (int i = 1; i <= scc_cnt; i++) {
if (out[i]) a++;
if (in[i]) b++;
}
printf("%d\n", max(a, b));
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
init();
solve();
}
return 0;
}
最新文章
- angularJ之$filter过滤器
- information_schema.TABLES
- MaterialUp - 寻找材料设计灵感必备的网站
- JavaScript中捕获/阻止捕获、冒泡/阻止冒泡
- SAP ALV OO 选择行打印
- DL4J (DeepLearning for java)
- Linux下编译内核配置选项简介
- 解决“运行arm-linux-gcc命令,提示No such file or directory”的问题
- java基础知识回顾之---java String final类普通方法的应用之“按照字节截取字符串”
- MySQL 大表优化方案探讨
- COJ 0358 xjr考考你数据结构(根号3)线段树区间修改
- 在基于阿里云serverCentOS6.5下安装Subversion 1.6.5服务
- HTTP请求响应机制与响应状态码
- python变量字符拼接
- Vue源码之----为什么Vue中Array的pop,push等方法可以reactive,而Array[0]=&#39;a&#39;这样的方法不会reactive?
- Codeforces1036G Sources and Sinks 【构造】【状态压缩】
- CSS 小技巧(不定时更新)
- HTML页面本地正常,部署到服务器稍微异常解决方案
- Python 特殊关系
- Android开发点滴 - 实现层级式导航(API 16+)