判断是不是强连通图。数据超级水，事实上随便写个dfs就能过了
添加最少数量的有向边把原图变成强连通图
这道题靠dfs果然已经水不过去了，于是只好老老实实学了一下tarjan (其实tarjan的精髓就是如何用栈？)
先tarjan把强连通分量缩点，得到有向无环图，设有a个点没有出度(方便起见称为叶子)，b个点没有入度(根)
则答案就是max(a,b)
假设a > b
首先呢，至少需要a条边，才有能让这a+b个点连通，
然后，从每个叶子引出一条边连向第一片叶子不能到达的叶子的根，最多用a-1条边，就可以让第一片叶子能够到达其他所有的叶子，
最后，把剩下的没有连出的叶子连向第一片叶子，就变成回路了
a < b的情况也类似
by the way，感觉强连通tarjan算法就是dfs树+栈，代码不长但是却处理了有向图的所有情况
和上一题是一个东西，只是换了一个背景
点有权，选出最少的点及最小的点权和，使得所有的点都能够被被选点通过有向边遍历到
scc缩个点先，得到新的有向无环图，新图的每个点的点权为对应原强连通分量中的最小点权
然后，最少点数就是新图入度为0的点的数量，最小点权和就是新图入度为0的点的权和
选择最小权边集，使得所有的点都能够被从0遍历(强连通分量费用为0)
显然先scc缩个点，新图的点权为原图连向该强连通分量的最小边权，0所在的强连通分量权值为0
答案就是新图的点权和
其实就是用最少的不相交有向路径覆盖强连通分量缩点后的所有的点
感觉tarjan在这里简直就是个模板，然后缩完点就没他什么事了= =
scc缩点，然后dfs遍历新图，当前节点与随便一个子节点共用一条路径，其他子节点则新开路径 (没什么最优性质，把父节点尽量往下连就好了。。)
然后输出答案
缩点，新图的点权为对应强连通分量内的点数量，
然后问题就变成怎么统计有向无环图的每个子树节点权和
这个。。暴力dfs就过去了= =
无可奈何时用暴力，大胆暴力出奇迹，暴力才是真爱啊。。
判断原图是不是有向仙人掌
有向图仙人掌：
1：强连通
2：每条边属于且只属于一个环
我先睡了一觉，然后起来先用tarjan判完强连通，然后yy了一个看起来很对的dfs瞬间就过去了。。
然后AC代码被某巨巨的神数据叉出了翔，然后又各种打补丁，现在看起来大概是木有问题了- -b
真尼玛欢乐的题目啊
附代码，有兴趣的童鞋帮我再叉一叉，有神数据请留言谢谢。。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define snuke(it,x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it ++)
const int N = 22222;
int stack[N],instack[N],top,tot,tim,dfn[N],low[N],n,vis[N],dep[N];
vector<int> G[N];
bool dfs(int u,int deep) {
vis[u] = 1;
dep[u] = deep;
snuke(it,G[u]) {
if (!instack[u]) {
instack[u] = 1;
stack[top++] = u;
}
int v = *it;
if (!vis[v]) {
if (!dfs(v,deep+1)) return false;
} else if (instack[v]) {
int pre = dep[u];
while (true) {
int c = stack[--top];
if (dep[c]!=pre) return false;
pre --;
instack[c] = 0;
if (c==v) break;
}
} else {
return false;
}
}
return true;
}
void tarjan(int u) {
dfn[u] = low[u] = ++tim;
stack[top++] = u;
instack[u] = 1;
snuke(it,G[u]) {
int v = *it;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u],low[v]);
} else if (instack[v]) {
low[u] = min(low[u],low[v]);
}
}
if (dfn[u]==low[u]) {
while (true) {
int c = stack[--top];
instack[c] = 0;
if (c==u) break;
}
tot ++;
}
}
void scc() {
tot = top = tim = 0;
memset(dfn,0,sizeof(dfn));
memset(instack,0,sizeof(instack));
for (int i = 0; i < n; i ++) if (!dfn[i]) tarjan(i);
}
int main() {
int cas;
scanf("%d",&cas);
while (cas--) {
scanf("%d",&n);
for (int i = 0; i < n; i ++) {
G[i].clear();
}
int a,b;
while (scanf("%d%d",&a,&b)==2 && (a||b)) {
G[a].push_back(b);
}
if (n==1) {
puts("YES");
continue;
}
scc();
if (tot>1) {
puts("NO");
continue;
}
top = 0;
memset(instack,0,sizeof(instack));
memset(vis,0,sizeof(vis));
bool ans = dfs(0,0);
puts(ans ? "YES" : "NO");
}
return 0;
}原文：http://blog.csdn.net/hei_nero/article/details/21477077