强连通分量
如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称 G 是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
常用于统计环的数量，割点割边。
割点（割顶）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int r_d(){
int x=0,f=1;
char c=getchar();
while(!isdigit(c)||c=='-'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
struct po{
int v;
int n_t;
}p_p[1000001];
int h_d[1000001],x_h;
void a_d(int u,int v){//存边
p_p[++x_h].v=v;
p_p[x_h].n_t=h_d[u];
h_d[u]=x_h;
}
int d_f[1000001],l_w[1000001],x_x;//d_f 时间戳 l_w 可以到达最小的时间戳（判环）
int c_c;
int s[1000001],top,b_l[1000001];
int g_d[1000001],r_r=0;
void t_j(int k){
d_f[k]=l_w[k]=++x_x;
int s_t=0;
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(!d_f[v]){
t_j(v);
l_w[k]=min(l_w[k],l_w[v]);
if(l_w[v]>=d_f[k]){//判断割点
s_t++;
if(s_t>=2||r_r!=k)g_d[k]=1;
}
}else {
l_w[k]=min(l_w[k],d_f[v]);
}
}
}
int a_s,n,m;
int main(){
n=r_d();m=r_d();
int u,v;
for(int i=0;i<m;i++){
u=r_d();v=r_d();
if(u==v)continue;
a_d(u,v);a_d(v,u);
}
for(int i=1;i<=n;i++)if(!d_f[i])r_r=i,t_j(i);//判断是否遍历过
for(int i=1;i<=n;i++)if(g_d[i])a_s++;
cout<<a_s<<endl;
for(int i=1;i<=n;i++)if(g_d[i])cout<<i<<" ";
cout<<endl;
return 0;
}割边
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int r_r(){
int x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=2e5+10;
int n,m;
struct po{
int v;
int n_t;
}p_p[o_o];
int h_d[o_o],x_p;
void a_d(int u,int v){//存边
p_p[++x_p].v=v;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
int l_w[o_o],d_f[o_o],x_x,f_f[o_o];
struct pp{
int l,r;
}a_s[o_o];
int x_a;
bool cmp(pp a,pp b){
return a.l==b.l?a.r<b.r:a.l<b.l;
}
void t_j(int k){
d_f[k]=l_w[k]=++x_x;
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(d_f[v]&&v!=f_f[k])l_w[k]=min(l_w[k],d_f[v]);//若果是祖先，割边就没用了
if(!d_f[v]){
f_f[v]=k;//建立祖先关系
t_j(v);
l_w[k]=min(l_w[v],l_w[k]);
if(l_w[v]>d_f[k])a_s[++x_a]={k,v};//割边判断条件
}
}
}
int main(){
n=r_r();m=r_r();
for(int i=1;i<=m;i++){
int a=r_r(),b=r_r();
a_d(a,b);
a_d(b,a);
}
for(int i=1;i<=n;i++)if(!d_f[i])t_j(i);//每个店都要遍历到，有时间戳
sort(a_s+1,a_s+1+x_a,cmp);//根据题目要求排序
for(int i=1;i<=x_a;i++)cout<<a_s[i].l<<" "<<a_s[i].r<<endl;
return 0;
}缩点
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int o_o=1e5+10;
int r_r(){
int x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int n,m;
int p_t[o_o];
struct po{
int v;
int n_t;
}p_p[o_o];
int h_d[o_o],x_p,i_a[o_o],i_b[o_o];
void a_d(int u,int v){
p_p[++x_p].v=v;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
int d_f[o_o],l_w[o_o],x_x,c_c,t_p,s_s[o_o],b_b[o_o];
int s_m[o_o],n_w[o_o];
void t_j(int k){
d_f[k]=l_w[k]=++x_x;//初始化时间戳
s_s[++t_p]=k;//存环中的点
b_b[k]=1;//是否遍历过
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(!d_f[v]){
t_j(v);
l_w[k]=min(l_w[k],l_w[v]);
}else if(b_b[v])l_w[k]=min(l_w[k],l_w[v]);//在同一环中
}
if(l_w[k]==d_f[k]){
++c_c;//新节点下标
while(s_s[t_p+1]!=k){//判断是否遍历完这个环
n_w[s_s[t_p]]=c_c;//赋新下标
s_m[c_c]+=p_t[s_s[t_p]];//存环节点的值的和（根据题目要求）
b_b[s_s[t_p--]]=0;
}
}
}
int f_f[o_o];
void f_i(int k){
if(f_f[k])return;
f_f[k]=s_m[k];
int m_a=0;
for(int i=h_d[k];i;i=p_p[i].n_t){//找最大值
int v=p_p[i].v;
if(!f_f[v])f_i(v);
m_a=max(m_a,f_f[v]);//更新
}
f_f[k]+=m_a;//累加答案
}
int a_s;
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n;i++)p_t[i]=r_r();
for(int i=1;i<=m;i++){//存初始边
i_a[i]=r_r();
i_b[i]=r_r();
a_d(i_a[i],i_b[i]);
}
for(int i=1;i<=n;i++)if(!d_f[i])t_j(i);
memset(p_p,0,sizeof p_p);//清空从新存新边
memset(h_d,0,sizeof h_d);
x_p=0;
for(int i=1;i<=m;i++)//不属于同一个环的连边（新点相当于原来的一个环）
if(n_w[i_a[i]]!=n_w[i_b[i]])a_d(n_w[i_a[i]],n_w[i_b[i]]);
for(int i=1;i<=c_c;i++){//便利每个新下标
if(!f_f[i]){
f_i(i);
a_s=max(f_f[i],a_s);//更新更优解
}
}
cout<<a_s<<endl;
return 0;
} 
