8/15 缩点+割点(割顶)+桥（割边）+字符串哈希

P3387 【模板】缩点

分三部分： 1.使用tarjan缩点，将各个强连通分量(分量内各店可相互到达)看作一个点。 2.建立缩点后的拓扑图，这些连通分量间也存在连线。 3.由于tarjan的出栈操作，当dfn==low是出栈被标记，标记值是由小到大的。先被标记的值小。 因此要在拓扑图上逆序dp

#include
#define endl '\n'
#define re register
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define maxn 1000000000LL
using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e7+7;
vectore[N],ne[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
int n,m,a[N],val[N],dp[N];
void tarjan(int x)
{
    //盖戳、入栈
    dfn[x]=low[x]=++tot;
    stk[++top]=x,instk[x]=1;
    for(int y:e[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            //回x时及时更新low
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) //若x已访问且在栈中
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]) //若x时SCC的根
    {
        int y;++cnt;
        do{
            y=stk[top--];instk[y]=0; //出栈
            scc[y]=cnt; //SCC编号
            ++siz[cnt];
            val[cnt]+=a[y];
        }while(y!=x);
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i>a[i];
    for(int i=1;i>u>>v;
        e[u].push_back(v);
    }
    for(int i=1;im;
    for(int i=1;i>u>>v;
        e[u].push_back(v),e[v].push_back(u);
    }
    for(int i=1;ix,a[x]=1;
    for(int i=1,x;i>x,b[x]=1;
    for(int i=1,u,v;i>u>>v;add(u,v),add(v,u);
    }
    tarjan(1,2);
    cout