每个强连通分量记最小值,及最小值的个数。
#includeusing namespace std; #define N 100010 #define M 300010 #define inf 0x3f3f3f3f #define ll long long const int mod=1e9+7; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int n,m,w[N],h[N],num=0,dfn[N],low[N],dfnum=0,bel[N],scc=0,sw[N],size[N]; ll ans1=0,ans2=1; bool inq[N]; stack q; struct edge{ int to,next; }data[M]; void tarjan(int x){ dfn[x]=low[x]=++dfnum;q.push(x);inq[x]=1; for(int i=h[x];i;i=data[i].next){ int y=data[i].to; if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);} else if(inq[y]) low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]){ ++scc;sw[scc]=inf;while(1){ int y=q.top();q.pop();inq[y]=0;bel[y]=scc; if(w[y]==sw[scc]) size[scc]++; if(w[y]