特工 007 在敌人内部发展了 N 个内线（给他提供情报的人），这些内线分别从 1 到 N 标号。这些内线有些是互相认识的。现在，007 为了处理和内线们复杂的关系，想把他们划分成尽量多的集合，要求任意两个属于不同集合的内线都必须互相认识，这样方便交流。现在007 想知道最多可以分成多少个集合，每个集合的人数是多少。
输入第一行是两个数 N 和 M。 接下来 M 行，每行两个整数，表示这两个内线是互相认识的。
第一行一个数 S ，表示最多有多少个集合。 第二行 S 个数，从小到大，表示每个集合的人数。
输入 [复制]
3 2 1 2 2 3输出
2 1 2【样例说明】 最多分成 2 个集合，分别如下： 集合 1：{2} 集合 2：{1,3} 2 认识 1，2 也认识 3
【数据范围】 对于 30% 的数据，1≤N≤500，1≤M≤100000 ； 对于 40% 的数据，1≤N≤1000，1≤M≤500000； 对于 100% 的数据，1≤N≤100000，1≤M≤2000000；
题目性质 ： 合法性:任意一个元素必须和非本集合的其他元素有边. 最优性:划分的集合个数最多. 解法一：Tarjan 题目分析: 考虑任意两点: 1：假如两个点之间没有连边，那么这两个点必然要在一个集合当中，这是很显然的，否则必然不符合题目的合法性。 2：假如两个点之间有连边，那么这两个点在与不在一个集合均合法，但如果它们在同一个集合中，其方案一定小于等于最优方案，即尽可能将有连边分到不同的集合中。 引入定义 : 补图：原图中存在的边变成不存在，不存在的边变成存在。 得到算法 : 先作出原图的补图。然后在补图中找出连通块，将同一连通块的点全部划分到一个集合。 理由：对于任意一个点i,如果i所属的连通块中点的个数不为1，则肯定存在一个和i相同集合的点j，且i和j在原图中没有边，使得按照题意，两个点必须在同一集合。同时，任意一个连通块中的任意一点到其他连通块中任意一点必定都有边。 满足题目的合法性和最优性，算法是正确。 时空复杂度 : 现在来面对另外一个瓶颈－－空间复杂度和时间复杂度。 数据规模中，点数N高达100000，边数M为2000000，可知原图是个稀疏图，则在补图中，边数则高达100000*100000-2000000，是一个边数非常密集的图。 如果直接构造补图，需10G的内存空间，显然是不可能实现的。所以，只能从原图的边信息中来判断补图的信息。 在时间上，无论是BFS还是DFS，复杂度都为O(M)，而补图的边数是超越longint的数，显然时间复杂度过高。 缩小规模 : 以上的瓶颈，根本原因是：数据规模过大。 只能尝试着缩小数据规模。 回过头来，再从题目的特殊性质和要求入手。 算法要求的是连通块，如果把同一连通块内的某些点缩合变成一个点，称为超级点。将原来和被缩点有关的边信息赋予超级点。可达到缩小数据规模又不影响解的正确性的目的。 关键要缩哪个连通块？缩哪些点呢？ 缩点的时侯，必然会访问边信息，而处理一遍所有的边信息，复杂度就可高达原图的O(M)。 所以，这样的处理，最多只能做一次。 再次分析题目，补图是高度稠密的，而原图是很稀疏的。即补图中点的度数都非常大，而度数最大的点的度数接近点数，其中最坏的情况是所有点度数平均。 极限数据中，补图平均度数是100000-4000000/100000=99960 换句话说，如果把这99960个点都缩进这个度数最大的点中，那么，只会剩下40个不同的点。多好！ 缩点效果最差的情况，出现在边为2000000,点为2000时，补图平均度数为2000-4000000/2000=0， 也就是原图为2000个点的完全图，补图为2000个孤立点。 所以，最坏情况，是缩成一个有2000个点的图。 选择进行一次缩点预处理：找出原图中度数最小的点，把原图中和它没有直接连边的点，都缩进它里头去。 一种比较贪的思想，能否不断的缩点达到结果呢？ 事实上，这样的操作只能做一次，因为做一次的复杂度已经高达O(M)。做多了，时间复杂度很容易变高。 而且，这样的操作做一次也已经足够，因为效果是惊人的，点数从100000下降到2000 之后不论是枚举，BFS，DFS，都可以轻松惬意地解决这个问题了…… 这里的算法选择实际用上了折中的思想，达到效果即可。 算法： 1、在原图中选择一个度最小的点，将与其无连边的点缩成一个超级点，把图的规模减小到2000点以内，可用邻接矩阵解决； (1)读入输入信息 (2)扫描一遍边的信息,对于每条边,两个端点度数+1,找出度数最小的点,设其为Imin (3) 扫描一遍边的信息,对于没有边和Imin直接相连的点,缩进Imin.设原图有N个点,其中没有边和Imin直接相连的点有num个。 2、超级点记录缩进各点的信息重构原图，如何重构是一个关键。 (1) 新开一张图G,规模为(N-num)*(N-num),初始值全部为0 (2)定义数组father[],上面提到的num个点以及Imin点本身,father值为1,其他点的father值依次标为2,3,4,5.... (3)再次扫描边的信息,对于每条边(u,v),如果father[u]!=father[v]进行操作:map[father[u]][father[v]]=1, map[father[v]][father[u]]=1; (4)补图G构建完成.map[i][j]=1表示补图中i,j有边直接相连.否则表示i,j没有边直接相连. 3、进行DFS(BFS),找出补图中连通块的个数,和每个连通块的点数。 下面是代码： #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <cmath> #include <cctype> #include <ctime> #include <queue> #include <stack> using namespace std; const int Max=2000001; stack <int> zhan; int n,m,ans,q=1,p=0,s=0,index=0,dian; //index:时间戳 dian:度数最小的点 ans:连通块个数 s:边的数量 int low[Max],num[Max],first[Max]; // low数组和num数组用于Tarjan first[i]:从i点出发的最后一条边 int map[3000][3000]; //map新建的图 int father[Max],r[Max],a[Max]; //a[i]:第i个联通块点的个数 father:新建图的编号 r:统计度数 bool exist[Max]; struct tarjan{int to,next;}; tarjan bian[Max << 1]; int get_int() //读入优化 { int x=0; char c; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } void build(int x,int y) { s++; bian[s].next=first[x]; first[x]=s; bian[s].to=y; } void read() { n=get_int(); m=get_int(); for(int i=1;i<=m;i++) { int x,y; x=get_int(); y=get_int(); build(x,y); build(y,x); r[x]++; //统计度数 r[y]++; //统计度数 } } void prepare() //缩点 { dian=1; for(int i=1;i<=n;i++) if(r[dian]>r[i]) dian=i; //;找度数最小的点 int k=first[dian]; memset(exist,0,sizeof(exist)); while(k!=-1) //遍历信息 { exist[bian[k].to]=true; k=bian[k].next; } for(int i=1;i<=n;i++) //创建新的编号 if(exist[i]==true) { q++; father[i]=q; } else { p++; father[i]=1; } } void rebuild() //重新建图 { int k=first[dian]; while(k!=-1) { memset(exist,0,sizeof(exist)); exist[bian[k].to]=true; int k1=first[bian[k].to]; while(k1!=-1) { exist[bian[k1].to]=true; k1=bian[k1].next; } for(int i=1;i<=n;i++) if(exist[i]==false&&father[bian[k].to]!=father[i]) { map[father[bian[k].to]][father[i]]=1; map[father[i]][father[bian[k].to]]=1; } k=bian[k].next; } } void tarjan(int x) //用Tarjan找连通块的个数及每个连通块点的数量 { index++; low[x]=index; num[x]=index; exist[x]=true; zhan.push(x); for(int i=1;i<=q;i++) if(map[x][i]) { if(num[i]==0) { tarjan(i); low[x]=min(low[x],low[i]); } else if(exist[i]) low[x]=min(low[x],num[i]); } if(low[x]==num[x]) { int i=zhan.top(),num=0; ans++; while(i!=x) { exist[i]=false; if(i==1) num+=p-1; num++; zhan.pop(); i=zhan.top(); } exist[i]=false; if(i==1) num+=p-1; num++; zhan.pop(); a[ans]=num; } } void solve() { memset(exist,0,sizeof(exist)); for(int i=1;i<=q;i++) if(num[i]==0) tarjan(i); } void out() { sort(a+1,a+ans+1); cout<<ans<<endl; for(int i=1;i<=ans;i++) cout<<a[i]<<" "; } main() { //freopen("lx.in","r",stdin); //freopen("lx.out","w",stdout); memset(low,0,sizeof(low)); memset(num,0,sizeof(num)); memset(first,-1,sizeof(first)); memset(map,0,sizeof(map)); memset(father,0,sizeof(father)); memset(r,0,sizeof(r)); memset(a,0,sizeof(a)); read(); prepare(); rebuild(); solve(); out(); return 0; }
总结： 本题的大致算法很容易想到－－做补图找连通块。而瓶颈和考点是缩小数据规模。在遇到瓶颈时，仔细分析题目的特点： 1、求连通块 2、补图高度稠密 从而找到缩小规模的方法。
解法二：并查集 用并查集的方法做不仅代码量少（缩到了100行），并且运行时间也差不多，直接附上代码： #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <cmath> #include <cctype> #include <ctime> #include <queue> using namespace std; int n,m,ans,s=1,minn=1; int father[1000005],first[1000005],a[1000005],num[1000005]; bool b[1000001],b1[1000001]; struct neixian{int next,to;}; neixian bian[8000001]; int get_int() //读入优化 { int x=0; char c; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } void build(int x,int y) { s++; bian[s].next=first[x]; first[x]=s; bian[s].to=y; } int getfather(int v) { if(father[v]==v) return v; father[v]=getfather(father[v]); return father[v]; } void search(int x) { memset(b1,false,sizeof(b1)); int u=first[x]; while(u!=-1) { b1[bian[u].to]=true; u=bian[u].next; } int p=getfather(x); for(int i=1;i<=n;i++) if(b1[i]==false) father[getfather(i)]=p; } int main() { //freopen("lx.in","r",stdin); //freopen("lx.out","w",stdout); memset(father,0,sizeof(father)); memset(first,-1,sizeof(first)); memset(bian,0,sizeof(bian)); memset(num,0,sizeof(num)); memset(b,false,sizeof(b)); n=get_int(); m=get_int(); for(int i=1;i<=m;i++) { int x=get_int(); int y=get_int(); build(x,y); build(y,x); num[x]++; num[y]++; } for(int i=1;i<=n;i++) if(num[minn]>num[i]) minn=i; for(int i=1;i<=n;i++) father[i]=i; int k=first[minn]; while(k!=-1) { search(bian[k].to); b[bian[k].to]=true; k=bian[k].next; } int p=getfather(minn); for(int i=1;i<=n;i++) if(b[i]==false) father[getfather(i)]=p; for(int i=1;i<=n;i++) a[getfather(i)]++; for(int i=1;i<=n;i++) if(a[i]==0) a[i]=1e+8; sort(a+1,a+n+1); while(a[ans]!=1e+8) ans++; cout<<ans-1<<endl; for(int i=1;i<=ans-1;i++) cout<<a[i]<<" "; return 0; }