[测试题]等效集合-白红宇

[测试题]等效集合

阅读量：4677 次

发布时间：2019-06-09

本文共 2477 字，大约阅读时间需要 8 分钟。

Description

要使两个集合 A,B 是等效的,我们可以先让 A 成为 B 的子集,然后再让 B 成为 A 的子集,这样就完成了。

使用上面的方法,我们要让 N 个集合都等效:每一步,你可以让集合 X 成为 Y 的子集。注意,有一些集合是已经是其他集合的子集了。求操作最少需要经过多少步?

Input

输入包含多组测试数据,每组数据的第一行是两个整数 N,M,接下来 M 行,每行两个数 X,Y,表示集合 X 已经是 Y 集合的子集。

Output

对于每组测试数据,输出一行,一个数,表示最少要经过的步数

Sample Input

4 0

3 2

1 2

1 3

Sample Output

Hint

对于 50%的数据, N <= 2000 and M <= 5000

对于 100%的数据,N <= 20000 and M <= 50000

题解

把非强连通图变为强连通图至少需要加多少条边。

$DAG$性质：对于一个有向无环图，若想让它成为强连通图，至少需要添加$max(a,b)$，$a$为入度为$0$的边点的数量，$b$为出度为$0$的点的数量。

注意当图本身就是强连通图的时候，就不用添边了。

1 //It is made by Awson on 2017.10.12 2 #include  3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #define LL long long16 #define Min(a, b) ((a) < (b) ? (a) : (b))17 #define Max(a, b) ((a) > (b) ? (a) : (b))18 #define Abs(x) ((x) < 0 ? (-(x)) : (x))19 using namespace std;20 const int N = 20000;21 const int M = 50000;22 23 int n, m, u, v;24 int in[N+5], out[N+5];25 struct tt {26 int to, next;27 }edge[M+5];28 int path[N+5], top;29 int dfn[N+5], low[N+5], tim;30 int sccnum, sccno[N+5];31 int S[N+5], T;32 bool vis[N+5];33 34 void tarjan(int u) {35 dfn[u] = low[u] = ++tim;36 S[++T] = u; vis[u] = 1;37 for (int i = path[u]; i; i = edge[i].next) {38 if (vis[edge[i].to]) low[u] = Min(low[u], dfn[edge[i].to]);39 else if (!dfn[edge[i].to]) {40 tarjan(edge[i].to);41 low[u] = Min(low[u], low[edge[i].to]);42 }43 }44 if (dfn[u] == low[u]) {45 sccnum++;46 do {47 vis[S[T]] = 0;48 sccno[S[T]] = sccnum;49 if (S[T--] == u) break;50 }while(T);51 }52 }53 void add(int u, int v) {54 edge[++top].to = v;55 edge[top].next = path[u];56 path[u] = top;57 } 58 void work() {59 memset(in, 0, sizeof(in));60 memset(out, 0, sizeof(out));61 memset(path, 0, sizeof(path)); top = 0;62 memset(dfn, 0, sizeof(dfn));63 sccnum = 0;64 for (int i = 1; i <= m; i++) {65 scanf("%d%d", &u, &v);66 add(u, v);67 }68 for (int i = 1; i <= n; i++)69 if (!dfn[i]) tarjan(i);70 int cntin = 0, cntout = 0;71 for (int i = 1; i <= n; i++)72 for (int j = path[i]; j; j = edge[j].next)73 if (sccno[i] != sccno[edge[j].to])74 out[sccno[i]]++, in[sccno[edge[j].to]]++;75 for (int i = 1; i <= sccnum; i++)76 cntin += !in[i], cntout += !out[i];77 printf("%d\n", Max(cntin, cntout));78 }79 int main() {80 while (~scanf("%d%d", &n, &m)) work();81 return 0;82 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/7656110.html

你可能感兴趣的文章