码量略大。
题意就是求路径必经点。
tarjan缩点，所有的非割点只有是起点终点时才必经，直接开个ans数组就OK了。
至于割点，因为缩完点之后的图是vDcc和割点共同组成的，而且题目说连通，那就是棵树，直接树上差分，最后统计信息，输出时输出割点的val即可。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<stack> #include<set> #include<map> using namespace std; int read(){ int sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){ if(x=='-') f=-1; x=getchar(); }while(x>='0'&&x<='9'){ sum=sum*10+x-'0'; x=getchar(); }return sum*f; } struct EDGE{ int ed,nex; }edge[400020],edgec[800020]; int num,numc,first[100500],firstc[2005000]; int n,m,ques,nvcn; int dfn[100500],low[100500],sta[1005000],bl[100500],new_id[100500]; int ord,vccnum,top,ans[100500],val[200500],d[200500]; int f[1000500][20]; vector<int>vcc[100500]; bool cut[100500],v[200500]; void add(int st,int ed){ // cout<<"st="<<st<<" ed="<<ed<<endl; edge[++num].ed=ed; edge[num].nex=first[st]; first[st]=num; } void addc(int st,int ed){ // cout<<"stc="<<st<<" edc="<<ed<<endl; edgec[++numc].ed=ed; edgec[numc].nex=firstc[st]; firstc[st]=numc; } void tarjan(int x){ dfn[x]=low[x]=++ord; sta[++top]=x; int child=0; for(int i=first[x];i;i=edge[i].nex){ int y=edge[i].ed; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ child++; if((x==1&&child>=2)||(x!=1&&child>0)) cut[x]=1; vcc[++vccnum].push_back(x); int p; do{ p=sta[top--]; vcc[vccnum].push_back(p); }while(p!=y); } }else low[x]=min(low[x],dfn[y]); } } void bfs(int st){ queue<int>q; d[st]=1; q.push(st); while(!q.empty()){ int x=q.front();q.pop(); for(int i=firstc[x];i;i=edgec[i].nex){ int y=edgec[i].ed; if(d[y]) continue; d[y]=d[x]+1; f[y][0]=x; q.push(y); for(int j=1;j<=18;j++) f[y][j]=f[f[y][j-1]][j-1]; } } } int lca(int x,int y){ if(d[x]>d[y]) swap(x,y); for(int i=18;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i]; if(x==y) return x; for(int i=18;i>=0;i--) if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; } return f[x][0]; } void dfs(int x){ v[x]=1; for(int i=firstc[x];i;i=edgec[i].nex){ int y=edgec[i].ed; if(v[y]) continue; dfs(y); val[x]+=val[y]; } } int main(){ // freopen("b.in","r",stdin); // freopen("b1.in","r",stdin); n=read();m=read();ques=read(); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); add(x,y);add(y,x); } tarjan(1); nvcn=vccnum; for(int i=1;i<=n;i++) if(cut[i]) new_id[i]=++nvcn; for(int i=1;i<=vccnum;i++) for(int j=0;j<vcc[i].size();j++){ int x=vcc[i][j]; if(cut[x]){ addc(new_id[x],i); addc(i,new_id[x]); }else bl[x]=i; } bfs(1); for(int i=1,a,b;i<=ques;i++){ a=read();b=read(); ans[a]++;ans[b]++; if(cut[a]) a=new_id[a]; else a=bl[a]; if(cut[b]) b=new_id[b]; else b=bl[b]; int LCA=lca(a,b); val[a]++;val[b]++;val[LCA]--;val[f[LCA][0]]--; } dfs(1); for(int i=1;i<=n;i++){ if(cut[i]) printf("%d ",val[new_id[i]]); else printf("%d ",ans[i]); }return 0; }