传送门：

解题思路：

题目大意是你能最多能添加多少边，使的这个图不是强连通图。其临界条件是差一条边成强连通图。

可以把图分成两个强连通图，左边的一个强连通分量点个数为y，右边一个强连通分量的个数为x。

然后x的所有点都与y的所有点都有x->y连线,没有y-x的连线。这就是最终答案。

x+y=n

x×（x-1）+y×（y-1）+x×y-m

化简的 n×n-x×y-n-m，很明显只有|x-y|的绝对值越大，最终结果就越大。

最后我们用Tarjan算法，进行缩点后可能形成现在这样的图

很明显只有入度，或出度为零的点才能选做x，或y。

实现代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 const int MAXN=100010;  8   9 struct Edge{ 10     int to,next; 11 }edges[MAXN]; 12  13 int head[MAXN],tot; 14  15 void init(){ 16     memset(head,-1,sizeof(head)); 17     tot=0; 18 } 19  20 void addEdge(int u,int v){ 21     edges[tot].to=v; 22     edges[tot].next=head[u]; 23     head[u]=tot++; 24 } 25  26 int DFN[MAXN],LOW[MAXN],Stack[MAXN],NUM[MAXN],Belong[MAXN]; 27 bool Instack[MAXN]; 28 int scc,Index,top; 29  30 void Tarjan(int u){ 31     DFN[u]=LOW[u]=++Index; 32     Stack[top++]=u; 33     Instack[u]=true; 34  35     int v; 36     for(int i=head[u];i!=-1;i=edges[i].next){ 37          v=edges[i].to; 38  39         if(!DFN[v]){ 40             Tarjan(v); 41             if(LOW[u]>LOW[v]) 42                 LOW[u]=LOW[v]; 43         }else if(Instack[v]&&LOW[u]>DFN[v]) LOW[u]=DFN[v]; 44     } 45  46     if(LOW[u]==DFN[u]){ 47         scc++; 48         do{ 49             v=Stack[--top]; 50             NUM[scc]++; 51             Instack[v]=false; 52             Belong[v]=scc; 53         }while(v!=u); 54     } 55 } 56  57 int in[MAXN],out[MAXN]; 58 void solve(long long n,long long m){ 59     memset(DFN,0,sizeof(DFN)); 60     memset(NUM,0,sizeof(NUM)); 61     memset(Instack,0,sizeof(Instack)); 62     top=Index=scc=0; 63  64     for(int i=1;i<=n;i++) 65         if(!DFN[i]) 66             Tarjan(i); 67  68     if(scc==1){ 69         cout<<-1<