当前位置：网站首页>hdu4635 Strongly connected (tarjan calculates strongly connected components + shrink points + ideas)

hdu4635 Strongly connected (tarjan calculates strongly connected components + shrink points + ideas)

2022-08-08 09:02:00 【51CTO】

Strongly connected

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2714 Accepted Submission(s): 1128

Problem Description

Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can add that the graph is still a simple directed graph. Also, after you add these edges, this graph must NOT be strongly connected.
A simple directed graph is a directed graph having no multiple edges or graph loops.
A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point.

Input

The first line of date is an integer T, which is the number of the text cases.
Then T cases follow, each case starts of two numbers N and M, 1<=N<=100000, 1<=M<=100000, representing the number of nodes and the number of edges, then M lines follow. Each line contains two integers x and y, means that there is a edge from x to y.

Output

For each case, you should output the maximum number of the edges you can add.
If the original graph is strongly connected, just output -1.

Sample Input

Sample Output

       
       Case 1: -1
       
Case 2: 1
       
Case 3: 15
      
1.
2.
3.

Source

2013 Multi-University Training Contest 4

Recommend

zhuyuanchen520 | We have carefully selected several similar problems for you: 6022 6021 6020 6019 6018

Statistic |

Submit |

Discuss |

Note

题意大概就是：给你一个DAG图,After asking how many edges to add at mostDAGThe graph is still not strongly connected.

对于这道题而言.We can think in reverse.If the graph is a strongly connected graph,So how many edges can there be at most.

Assuming the last requestedDAGThe figure has two partsX图和Y图.此时X图和YEach graph must be a strongly connected graph,并且X图和YThere are only one-way edges between graphs.

这样才能使DAGThe maximum number of graph edges

假设X图的顶点数为x,Y图的顶点数为y,则DAG图的顶点数为x+y=n

则有：

如果使XGraph Strongly Connected,边数最多为x*(x-1)(即Xto each vertex of the graphXEvery other vertex of the graph has a one-way edge)
如果使YGraph Strongly Connected,边数最多为y*(y-1)
X图和YThere are only single-item edges between graphs,The maximum number of sides is x*y(即Xto each vertex of the graphYEach vertex of the graph has a one-way edge)

The number of sides can be obtained from the aboveF（DAG）=x*y+x*(x-1)+y*(y-1)=n*n-n-x*y.即DAGThe maximum number of edges in the graph is n*n-n-x*y.

由于n一定,So this question can be transformed into a requestx*y的最小值,又因为x+y=n.所以x和yThe larger the difference, the smaller the result.

Then this question turns into a searchDAGThe smallest strongly connected component of a vertex in a graph.

F（DAG）Subtract the number of existing edgesmThat is the desired result.

Compute strongly connected components can be usedtarjan算法,In the statistical process, the strongly connected components can be shortened~由于我们要求X图和YThere are only one-way edges between graphs,所以

我们要找的Y图 Must be in-degree0或者出度为0的强连通分量,否则此DAGThe graph is a strongly connected graph .

代码如下：

       
       #include <stdio.h>
       
       #include <vector>
       
       #include <stack>
       
       #include <algorithm>
       
       #include <string.h>
       
       using 
       
       namespace 
       
       std;
       
       #define N 100000+10
       
       vector
       
       <
       
       int
       
       >
       
       link[
       
       N];
       
       bool 
       
       inStack[
       
       N];
       
       int 
       
       dfn[
       
       N];
       
       int 
       
       low[
       
       N];
       
       int 
       
       fa[
       
       N];
       
       //通过DAG图中 The number of the strongly connected component to which a vertex belongs 
       
       int 
       
       point[
       
       N];
       
       //Count the number of vertices of a strongly connected component after shrinking 
       
       int 
       
       in[
       
       N];
       
       //The in-degree of a strongly connected component after the contraction point 
       
       int 
       
       out[
       
       N];
       
       //The out-degree of a strongly connected component after the contraction point 
       
       int 
       
       time;
       
       //时间戳 
       
       int 
       
       sum;
       
       //DAGThe number of connected components in the graph 
       
       int 
       
       n,
       
       m;
       
       stack
       
       <
       
       int
       
       >
       
       s;
       
       void 
       
       doTarjan(
       
       int 
       
       x)
       
{
       
       dfn[
       
       x]
       
       =
       
       low[
       
       x]
       
       =++
       
       time;
       
       s.
       
       push(
       
       x);
       
       inStack[
       
       x]
       
       =
       
       true;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       link[
       
       x].
       
       size();
       
       i
       
       ++)
       
  {
       
       int 
       
       edge
       
       =
       
       link[
       
       x][
       
       i];
       
       if(
       
       !
       
       dfn[
       
       edge])
       
    {
       
       doTarjan(
       
       edge);
       
       low[
       
       x]
       
       =
       
       min(
       
       low[
       
       x],
       
       low[
       
       edge]);
       
    }
       
       else 
       
       if(
       
       inStack[
       
       edge])
       
    {
       
       low[
       
       x]
       
       =
       
       min(
       
       low[
       
       x],
       
       dfn[
       
       edge]);
       
    }
       
  }
       
       if(
       
       dfn[
       
       x]
       
       ==
       
       low[
       
       x])
       
  {
       
       sum
       
       ++;
       
       //Strongly connected component sequence number 
       
       int 
       
       u;
       
       do
       
    {
       
       u
       
       =
       
       s.
       
       top();
       
       s.
       
       pop();
       
       inStack[
       
       u]
       
       =
       
       false;
       
       fa[
       
       u]
       
       =
       
       sum;
       
       //缩点 
       
    }
       
       while(
       
       u
       
       !=
       
       x);
       
  }
       
}
       
       int 
       
       solve()
       
{
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++)
       
  {
       
       if(
       
       !
       
       dfn[
       
       i])
       
       doTarjan(
       
       i);
       
  }
       
       //如果DAGThe graph is already a strongly connected graph 直接返回-1 
       
       if(
       
       sum
       
       ==
       
       1) 
       
       return 
       
       -
       
       1;
       
       //Computes the in-degree of the strongly connected components after condensed points、out-degree and vertex count 
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++)
       
  {
       
       point[
       
       fa[
       
       i]]
       
       ++;
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       link[
       
       i].
       
       size();
       
       j
       
       ++)
       
    {
       
       if(
       
       fa[
       
       i]
       
       ==
       
       fa[
       
       link[
       
       i][
       
       j]]) 
       
       continue;
       
       in[
       
       fa[
       
       link[
       
       i][
       
       j]]]
       
       ++;
       
       out[
       
       fa[
       
       i]]
       
       ++;
       
    }
       
  }
       
       int 
       
       res
       
       =-
       
       1;
       
       //在这里一定要注意 我们要找的Y图 Must be in-degree0或者出度为0的强连通分量
       
       //否则 此DAGThe graph is a strongly connected graph 
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       sum;
       
       i
       
       ++)
       
  {
       
       if(
       
       in[
       
       i]
       
       &&
       
       out[
       
       i]) 
       
       continue; 
       
       res
       
       =
       
       max(
       
       res,
       
       n
       
       *
       
       n
       
       -
       
       n
       
       -(
       
       n
       
       -
       
       point[
       
       i])
       
       *
       
       point[
       
       i]
       
       -
       
       m);
       
  }
       
       return 
       
       res;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       t,
       
       cnt
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       while(
       
       t
       
       --)
       
  {
       
       time
       
       =
       
       sum
       
       =
       
       0;
       
       memset(
       
       fa,
       
       0,
       
       sizeof(
       
       fa));
       
       memset(
       
       in,
       
       0,
       
       sizeof(
       
       in));
       
       memset(
       
       out,
       
       0,
       
       sizeof(
       
       out));
       
       memset(
       
       dfn,
       
       0,
       
       sizeof(
       
       dfn));
       
       memset(
       
       low,
       
       0,
       
       sizeof(
       
       low));
       
       memset(
       
       link,
       
       0,
       
       sizeof(
       
       link));
       
       memset(
       
       point,
       
       0,
       
       sizeof(
       
       point));
       
       memset(
       
       inStack,
       
       false,
       
       sizeof(
       
       inStack));
       
       scanf(
       
       "%d %d",
       
       &
       
       n,
       
       &
       
       m);
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       m;
       
       i
       
       ++)
       
    {
       
       int 
       
       a,
       
       b;
       
       scanf(
       
       "%d %d",
       
       &
       
       a,
       
       &
       
       b);
       
       link[
       
       a].
       
       push_back(
       
       b);
       
    }
       
       printf(
       
       "Case %d: %d\n",
       
       ++
       
       cnt,
       
       solve());
       
  }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/220/202208080848250852.html

当前位置：网站首页>hdu4635 Strongly connected (tarjan calculates strongly connected components + shrink points + ideas)

hdu4635 Strongly connected (tarjan calculates strongly connected components + shrink points + ideas)

Strongly connected

边栏推荐

猜你喜欢

随机推荐