tarjan算法可以求有向图的割点割边强连通分量（还有一些奇奇怪怪的操作）
我只会割点和强连通分量，割边（和缩点）以后可能会加，如果是来看割边的话，现在跑还来得及。。
（先来一张有向图叭）
用这张图，我们来解释一些东西：
设在有向图G中，GG为其子图，u,v分别是G中的节点。
强连通：如果u可以到达v，v也可以到达u，那么u,v强连通。（比如2可以到达9,9可以通过9—10—3—2到达2）
强连通图：若G内各点都强连通，就说G是强连通图。
强联通分量：若GG是强连通图，就说它是G的强连通分量。
割点：设割去点u，G断成了多个图，就说u是G的割点。（如1）
所有的tarjan算法都要用到两个数组：
dfn[]：节点的dfs序；
low[]：该节点所在强连通分量中最小的dfn值，可以理解为团队主。
tarjan如何求强连通分量
首先要维护一个栈，来记录我们找过了哪些点。
然后遍历u的儿子
设v是u的子节点。
如果v没有走过，那么先遍历v的儿子
若v的团队主比u的团队主更高级（low[v]<low[u]）显然，u要顺从v的团队主；
否则u不变。
如果v已经处理过了在栈里了
若v比u更高级（dfn[v]<low[u]），显然，u要顺从v；
否则u不变，坐等v加入团队。
这一部分的代码：
inline void tarjan(int x){dfn[x]=low[x]=++num;//dfs序 st[++top]=x;v[x]=true;//入栈，v[x]标记x在栈内 for(register int i=head[x];i;i=e[i].nxt){if(!dfn[e[i].y]){tarjan(e[i].y);low[x]=min(low[x],low[e[i].y]);}else if(v[e[i].y])low[x]=min(low[x],dfn[e[i].y]);}
当考虑完团队划分整合之后，我们如何确定有几个团队呢
如果dfn[x]==low[x]，显然，x就是某个团队的团队主
此时我们需要++cnt（cnt代表目前团队编号），然后将x之后的数全部弹出栈，压入事先准备好的vector中（怎么觉得有点像做菜）。因为在x之后的点都是从x出发遍历到的，这些点之中没有可以改变low[x]的，显然他们都归顺于x。
这一部分的代码：
if(dfn[x]==low[x]){cnt++;int y;do{y=st[top--];v[y]=false;scc[cnt].push_back(y);}while(x!=y);}
讲完了算法，就可以愉快的来一道板子题了
牛的舞会
这个。。裸的掉牙了。
#include<iostream>#include<string>#include<cstdio>#include<cstring>#include<vector>#define maxn 10005#define maxm 50005using namespace std;int n,m,head[maxn],tot;int dfn[maxn],low[maxn],num,st[maxn],ans,top,cnt;bool v[maxn];struct node{int y,nxt;}e[maxm];inline void ad(int x,int y){e[++tot].y=y;e[tot].nxt=head[x];head[x]=tot;}vector<int> scc[maxn];inline void tarjan(int x){dfn[x]=low[x]=++num;//dfs序 st[++top]=x;v[x]=true;//入栈，v[x]标记x在栈内 for(register int i=head[x];i;i=e[i].nxt){if(!dfn[e[i].y]){tarjan(e[i].y);low[x]=min(low[x],low[e[i].y]);}else if(v[e[i].y])low[x]=min(low[x],dfn[e[i].y]);}if(dfn[x]==low[x]){cnt++;int y;do{y=st[top--];v[y]=false;scc[cnt].push_back(y);}while(x!=y);}}int main(){scanf("%d%d",&n,&m);int x,y;for(register int i=1;i<=m;i++){scanf("%d%d",&x,&y);ad(x,y);}for(register int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(register int i=1;i<=cnt;i++){if(scc[i].size()>1)++ans;}printf("%d",ans);}
tarjan如何求割点
（呜哇总算写完前半部分啦）
如果一个点是根节点，有多个子树，它肯定是个割点。
如果一个点不是根节点，它存在一个子树，无法连接更高级的团队主，那么这个点就是割点。
（可以这样想，割掉以后那棵子树无法和其他点连接，必然会产生新的块）
板子题
代码
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#define maxn 100005#define maxm 100005using namespace std;int n,m;int head[maxn],tot,root;int dfn[maxn],low[maxn],num,ans;bool cut[maxn];struct node{int y,nxt;}e[maxn<<1];inline void ad(int x,int y){e[++tot].y=y;e[tot].nxt=head[x];head[x]=tot;}inline void tarjan(int x){dfn[x]=low[x]=++num;int flag=0;for(register int i=head[x];i;i=e[i].nxt){int y=e[i].y;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);if(dfn[x]<=low[y]){flag++;if(x!=root||flag>1)cut[x]=true; }}else{low[x]=min(low[x],dfn[y]);}}}int main(){scanf("%d%d",&n,&m);int x,y;for(register int i=1;i<=m;i++){scanf("%d%d",&x,&y);ad(x,y);ad(y,x);}for(register int i=1;i<=n;i++){if(!dfn[i])root=i,tarjan(i);}for(register int i=1;i<=n;i++)if(cut[i])++ans;printf("%d\n",ans);for(register int i=1;i<=n;i++){if(cut[i])printf("%d ",i);}return 0;}
终于写完了qwq
flag插地：这周学会割边和缩点！
谢谢你可以看到这里呀
希望对你有所帮助
有写的不好或者不对的地方要及时指出来哦qwq
