【链接】 Codeforces 292D
【题目大意】 给你N个节点和M条边以及Q次询问。对于每一次询问给你两个数li,ri表示不取区间li~ri的边，并输出连通块的个数。
【解题报告】 因为li~ri里的边是不取的，求的又是连通块的个数，所以考虑要取的边。首先想到的是一个O(N*M*Q)的暴力直接搞，但是时间复杂度扛不住。这是就想到了预处理记l[i]表示1~i的边构成的图中每个节点的父亲是谁，r[i]表示i~n的边构成的图中每个节点的父亲是谁，预处理的时间复杂度为O(N*M)。所以对于每次询问就可以O(N)回答，时间复杂度O(N*Q)。
#include<cstdio> using namespace std; const int maxn=505,maxm=10005; int n,m,Q; struct wjd { int x,y; }a[maxm]; struct UF { int fa[maxn]; void Clear(){for (int i=1; i<=n; i++) fa[i]=i;} int Getfa(int x){if (fa[x]==x) return x; fa[x]=Getfa(fa[x]); return fa[x];} void Merge(int x,int y) {x=Getfa(x); y=Getfa(y); if (x!=y) fa[x]=y;} }L[maxm],R[maxm],Fa;//并查集 inline int Read() { int res=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar(); return res; } int Query(int l,int r) { for (int i=1; i<=n; i++) Fa.fa[i]=L[l].fa[i]; for (int i=1; i<=n; i++) Fa.Merge(i,R[r].Getfa(R[r].fa[i])); int sum=0; for (int i=1; i<=n; i++) if (i==Fa.Getfa(i)) sum++; return sum; } int main() {#include<cstdio> using namespace std; const int maxn=505,maxm=10005; int n,m,Q; struct wjd { int x,y; }a[maxm]; struct UF { int fa[maxn]; void Clear(){for (int i=1; i<=n; i++) fa[i]=i;} int Getfa(int x){if (fa[x]==x) return x; fa[x]=Getfa(fa[x]); return fa[x];} void Merge(int x,int y) {x=Getfa(x); y=Getfa(y); if (x!=y) fa[x]=y;} }L[maxm],R[maxm],Fa; inline int Read() { int res=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar(); return res; } int Query(int l,int r) { for (int i=1; i<=n; i++) Fa.fa[i]=L[l].fa[i]; for (int i=1; i<=n; i++) Fa.Merge(i,R[r].Getfa(R[r].fa[i])); int sum=0; for (int i=1; i<=n; i++) if (i==Fa.Getfa(i)) sum++; return sum; } int main() { freopen("292D.in","r",stdin); freopen("292D.out","w",stdout); n=Read(); m=Read(); for (int i=1; i<=m; i++) a[i]=(wjd){Read(),Read()}; L[0].Clear(); R[m+1].Clear(); for (int i=1; i<=m; i++) L[i]=L[i-1],L[i].Merge(a[i].x,a[i].y); for (int i=m; i; i--) R[i]=R[i+1],R[i].Merge(a[i].x,a[i].y); Q=Read(); for (int i=1; i<=Q; i++) { int l=Read(),r=Read(); printf("%d\n",Query(l-1,r+1)); } return 0; } n=Read(); m=Read(); for (int i=1; i<=m; i++) a[i]=(wjd){Read(),Read()}; L[0].Clear(); R[m+1].Clear(); for (int i=1; i<=m; i++) L[i]=L[i-1],L[i].Merge(a[i].x,a[i].y);//构造L数组 for (int i=m; i; i--) R[i]=R[i+1],R[i].Merge(a[i].x,a[i].y);//构造R数组 Q=Read(); for (int i=1; i<=Q; i++) { int l=Read(),r=Read(); printf("%d\n",Query(l-1,r+1)); } return 0; }