题目链接：hdu 4635 Strongly connected 解题思路 先对给定图做强联通分量，选取出度或者是入度为0的分量中点个数最少的一个，然后其它联通分量算一个，将图分成两部分，做完全图并保证两部分是之间的边均为单向边。 代码 #include <cstdio>#include <cstring>#include <vector>#include <stack>#incl

题目描述 小 H 在一个划分成了n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血 6 点，每移动一格他要消耗 1 点血量。一旦小 H 的血量降到 0， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所

#include <cstdio>#include <cstring>#include <set>using namespace std;/**在原有的有向连通图中插入尽可能多的边使其不是强连通 由于原图非强连通，因此至少存在一个强连通分支入度或出度为0。而且最后答案中的图中也应该存在这样的分支。通过添加边无法减少度，因此需要从度为0的分支中找出点数最少的并使其与外部的点相连且保留原属性

tarjan算法 最终添加完边的图，肯定可以分成两个部X和Y，其中只有X到Y的边没有Y到X的边，那么要使得边数尽可能的多，则X部肯定是一个完全图，Y部也是，同时X部中每个点到Y部的每个点都有一条边，假设X部有x个点，Y部有y个点，有x+y=n，同时边数F=x*y+x*(x-1)+y*(y-1)，整理得：F=N*N-N-x*y，当x+y为定值时，二者越接近，x*y越大，所以要使得边数最多，那么X部

一、内容 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 edge

题意： 给你一个有向图，问你最多能添加多少条边使得这个图依然不是强联通的。 做法： 1，求出图中的所有强连通分量 2，把上述的强连通分量缩成一个点。 3，问题现在变成问一个完全图，最少需要去除多少条边使得这个图不强联通，         那么肯定是去除所有强联通分量中含有点数最少的点的所有进边。 #include<stdio.h>#include<iostream>#in