hdu 3836 Equivalent Sets

时间:2022-03-04 23:50:27

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=3836

Equivalent Sets

Description

To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.

Input

The input file contains multiple test cases, in each case, the first line contains two integers N <= 20000 and M <= 50000.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.

Output

For each case, output a single integer: the minimum steps needed.

Sample Input

4 0
3 2
1 2
1 3

Sample Output

4
3

题目大意:给你一张有向图要求最少加多少条边时该图变成强连通图。
Tarjan缩点。。

#include<bits/stdc++.h>
using namespace std;
const int N = 20100;
struct Tarjan_scc {
stack<int> s;
bool instack[N];
struct edge { int to, next; }G[N * 3];
int idx, scc, tot, in[N], out[N], dfn[N], low[N], head[N], sccnum[N];
inline void init(int n) {
idx = scc = tot = 0;
while (!s.empty()) s.pop();
for (int i = 0; i < n + 2; i++) {
head[i] = -1;
instack[i] = false;
in[i] = out[i] = dfn[i] = low[i] = sccnum[i] = 0;
}
}
inline void add_edge(int u, int v) {
G[tot].to = v, G[tot].next = head[u], head[u] = tot++;
}
inline void built(int m) {
int u, v;
while (m--) {
scanf("%d %d", &u, &v);
add_edge(u, v);
}
}
inline void tarjan(int u) {
dfn[u] = low[u] = ++idx;
instack[u] = true;
s.push(u);
for (int i = head[u]; ~i; i = G[i].next) {
int &v = G[i].to;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v] && dfn[v] < low[u]) {
low[u] = dfn[v];
}
}
if (dfn[u] == low[u]) {
int v = 0;
scc++;
do {
v = s.top(); s.pop();
instack[v] = false;
sccnum[v] = scc;
} while (u != v);
}
}
inline void solve(int n, int m) {
init(n);
built(m);
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
int x1 = 0, x2 = 0;
for (int u = 1; u <= n; u++) {
for (int i = head[u]; ~i; i = G[i].next) {
int v = G[i].to;
if (sccnum[u] != sccnum[v]) {
in[sccnum[v]]++;
out[sccnum[u]]++;
}
}
}
for (int i = 1; i <= scc; i++) {
if (!in[i]) x1++;
if (!out[i]) x2++;
}
printf("%d\n", 1 == scc ? 0 : max(x1, x2));
}
}go;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
int n, m;
while (~scanf("%d %d", &n, &m)) {
go.solve(n, m);
}
return 0;
}

hdu 3836 Equivalent Sets的更多相关文章

  1. &lbrack;tarjan&rsqb; hdu 3836 Equivalent Sets

    主题链接: http://acm.hdu.edu.cn/showproblem.php? pid=3836 Equivalent Sets Time Limit: 12000/4000 MS (Jav ...

  2. hdu 3836 Equivalent Sets trajan缩点

    Equivalent Sets Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 104857/104857 K (Java/Other ...

  3. hdu 3836 Equivalent Sets(强连通分量--加边)

    Equivalent Sets Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 104857/104857 K (Java/Other ...

  4. hdu——3836 Equivalent Sets

    Equivalent Sets Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 104857/104857 K (Java/Other ...

  5. hdu 3836 Equivalent Sets(tarjan&plus;缩点)

    Problem Description To prove two sets A and B are equivalent, we can first prove A is a subset of B, ...

  6. hdu - 3836 Equivalent Sets&lpar;强连通&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=3836 判断至少需要加几条边才能使图变成强连通 把图缩点之后统计入度为0的点和出度为0的点,然后两者中的最大值就是 ...

  7. HDU - 3836 Equivalent Sets &lpar;强连通分量&plus;DAG&rpar;

    题目大意:给出N个点,M条边.要求你加入最少的边,使得这个图变成强连通分量 解题思路:先找出全部的强连通分量和桥,将强连通分量缩点.桥作为连线,就形成了DAG了 这题被坑了.用了G++交的,结果一直R ...

  8. hdoj 3836 Equivalent Sets【scc&amp&semi;&amp&semi;缩点】【求最少加多少条边使图强连通】

    Equivalent Sets Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 104857/104857 K (Java/Other ...

  9. HUD——T 3836 Equivalent Sets

    http://acm.hdu.edu.cn/showproblem.php?pid=3836 Time Limit: 12000/4000 MS (Java/Others)    Memory Lim ...

随机推荐

  1. Linux 学习记录

    整理学习Linux操作系统遇到的不理解的概念.逐个进行补充.我们用的版本是CentOs. what's the gcc? what's the yum? what's the wget?

  2. android 四大组件之---Service

    服务 服务的生命周期 --- 1 开启服务的生命周期 完整的生命周期:onCreate()-->onStartCommand()-->onDestroy() * 开启服务:onCreate ...

  3. ubuntu下安装jdk

    参考:http://blog.csdn.net/gobitan/article/details/24322561 Ubuntu Linux下安装Oracle JDK Dennis Hu 2014-4- ...

  4. C&num;&lowbar;abstract的用法

    /// <summary> /// 抽像类 /// </summary> public abstract class Hello { private string msg = ...

  5. url重写&lpar;伪静态&rpar;IIS配置图解

    通过IIS创建虚拟目录,新建网站放在该目录下面: IIS配置: 虚拟目录=>点击右键=>选择属性: 点击配置: 点击编辑: 复制两个文本框文本到记事本中=>点击确定: 点击添加=&g ...

  6. Spring IoC — 基于Java类的配置

    普通的POJO只要标注@Configuration注解,就可以为Spring容器提供Bean定义的信息了,每个标注了@Bean的类方法都相当于提供一个Bean的定义信息. 基于Java类的配置方法和基 ...

  7. linux 标准 GPIO 操作

    Linux 提供了GPIO 操作的 API,具体初始化及注册函数在 driver/gpio/lib_gpio.c 中实现.   #include    int gpio_request(unsigne ...

  8. javascript复制

    1.实现点击按钮,复制文本框中的的内容 1 <scrip type="text/javascript"> 2 function copyUrl2() 3 { 4 var ...

  9. Eclipse Web项目配置

    1.每次重开workspace都要重新配置一次 2.new web project之前配置 3.Windows-Preferences-(所有都要记得Apply) General   Maven P. ...

  10. 【温故知新】HTTP请求GET和POST的用法和区别

    转自http://www.w3school.com.cn GET的使用 请注意,查询字符串(名称/值对)是在 GET 请求的 URL 中发送的: /test/demo_form.asp?name1=v ...