[日常训练]冬眠营
Description
小$G$是个算法爱好者,他很高兴今年来到$M$市参加$WC$。
按照惯例,大家在$WC$上,都是来冬眠的。然而今年情况有些特殊,并不是因为难度太大大家纷纷弃疗,而是因为正在讲的问题太水太简单了。
正在讨论的题目是这样的:给你一个$n$个点$m$条边的无向图,点和边都从$0$开始编号。共$Q$次询问,每次询问一个编号$x$,要求回答删去编号为$x$的边后,会有多少个无序点对$(u, v)$将不能相互到达?
小$G$觉得太简单就去冬眠了,而你能解出这题吗?
Input
第一行三个整数$n,m$,$Q$分别代表点数边数询问数。
接下来$m$行每行两个整数$u,v$表示$u$与$v$之间有一条边。注意可能有重边
和自环。
接下来$Q$行每行一个整数$x$表示询问的边的编号。
Output
输出$Q$行每行一个整数,表示询问的答案,结果保留后三位。
Sample Input
4 3 3
0 1
1 0
0 2
0 1 2
Sample Output
3
3
5
HINT
$1\;\leq\;n\;\leq\;10^5,1\;\leq\;m\;\leq\;10^6,1\;\leq\;Q\;\leq\;8\;\times\;10^5,0\;\leq\;u,v
Solution
预处理出本身就不联通的点对个数$sum$,处理出每条边是不是割边.
如果是割边答案为$sum+\prod$(割去这条边新产生的连通块大小).
#include#include #include #include #include #include #include #include #include #include #define K 1000 #define N 100005 #define M 2000005 using namespace std; struct graph{ int nxt,to,n; }e[M]; int g[N],l[M],r[M],dfn[N],low[N]; int s[N],s1[N],s2[N],n,m,k,sum,cnt=1; int siz[N],tot[M],top; bool v[N],cut[M]; queue<int> q; inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-'0'; c=getchar(); } return ret; } inline void addedge(int x,int y,int n){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].n=n; } inline void tarjan(int u,int k){ dfn[u]=low[u]=++cnt;siz[u]=1; for(int i=g[u];i;i=e[i].nxt) if(!dfn[e[i].to]){ tarjan(e[i].to,i>>1); siz[u]+=siz[e[i].to]; low[u]=min(low[u],low[e[i].to]); if(low[e[i].to]>dfn[u]){ cut[e[i].n]=true; tot[e[i].n]=siz[e[i].to]; } } else if((i>>1)!=k) low[u]=min(low[u],dfn[e[i].to]); } inline int bfs(int u){ int ret=0,p=u; q.push(u);v[u]=true; while(!q.empty()){ u=q.front();q.pop();++ret; for(int i=g[u];i;i=e[i].nxt) if(!v[e[i].to]){ v[e[i].to]=true; q.push(e[i].to); } } q.push(p);v[p]=ret; while(!q.empty()){ u=q.front();q.pop(); for(int i=g[u];i;i=e[i].nxt) if(!s[e[i].to]){ s[e[i].to]=ret; q.push(e[i].to); } } return ret; } inline void Aireen(){ n=read();m=read();k=read(); for(int i=1,t;i<=m;++i){ l[i]=read()+1;r[i]=read()+1; if(l[i]!=r[i]){ addedge(l[i],r[i],i); addedge(r[i],l[i],i); } } cnt=0; for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0); cnt=0; for(int i=1,t;i<=n;++i) if(!v[i]) s1[++cnt]=bfs(i)%K; for(int i=1;i<=cnt;++i) s2[i]=(s2[i-1]+s1[i])%K; for(int i=1;i<=cnt;++i) sum=(sum+s1[i]*(s2[cnt]-s2[i]+K))%K; // 求割边 for(int x;k--;){ x=read()+1; if(cut[x]) printf("%d\n",(sum+tot[x]%K*((s[l[x]]-tot[x])%K))%K); else printf("%d\n",sum); } } int main(){ freopen("wc.in","r",stdin); freopen("wc.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }