题目大意：给出仙人掌图的定义：
1.必须是强连通
2.每条边只能属于一个环

解题思路：在tarjan算法中加入点东西就可以判断了
只要该点能连到之前的点，那么形成环了，找到这个环的所有的边，并标记
如果有一条边被标记了两次了，那图就不是仙人掌图了

关键是怎么找到这个环的所有边，我们可以引入另一个栈，这个栈存放的是边的序号
假设当前点为u，u点连回之前的点是v，那么就从栈里面找边，找到出发点为v的边为止，找到的这些边都是环上的边，这个和tarjan算法的找同一个连通分量的点的道理是一样

#include 
   
     #include 
    
      #pragma comment(linker, /STACK:102400000,102400000) #define N 20010 #define M 50010 #define min(a,b) ((a) < (b) ? (a) : (b)) struct Edge{ int from, to, next, id; }E[M]; int head[N], pre[N], lowlink[N], sccno[N], stack[N], stack2[M]; int tot, n, scc_cnt, dfs_clock, top, top2; int queue[M]; bool vis[M]; bool flag; void AddEdge(int from, int to) { E[tot].from = from; E[tot].to = to; E[tot].next = head[from]; E[tot].id = tot; head[from] = tot++; } void init(){ scanf(%d, &n); memset(head, -1, sizeof(head)); tot = 0; int u, v; while (scanf(%d%d, &u, &v) && u + v) { AddEdge(u, v); } } void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; stack[++top] = u; for (int i = head[u]; i != -1; i = E[i].next) { int v = E[i].to; stack2[++top2] = E[i].id; if (!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); int tmp = top2; while (1){ int id = stack2[top2--]; if (vis[id]) flag = true; vis[id] = true; if (E[id].from == v) break; } top2 = tmp; } top2--; } int x; if (pre[u] == lowlink[u]) { scc_cnt++; while (1) { x = stack[top--]; sccno[x] = scc_cnt; if (x == u) break; } } } void solve() { memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); memset(vis, 0, sizeof(vis)); dfs_clock = top = top2 = scc_cnt = 0; flag = false; dfs(0); for (int i = 0; i < n; i++) { if (sccno[i] != 1) { printf(NO ); return ; } } if (flag) printf(NO ); else printf(YES ); } int main() { int test; scanf(%d, &test); while (test--) { init(); solve(); } return 0; } 
    
   

?