冒泡排序图
问题描述:
有一段使用冒泡排序产生一张图的伪代码如下：
function bubbleSortGraph(n, a[]):
graph = emptyGraph()
repeat
swapped = false
for i = 1 to n - 1:
if a[i] > a[i + 1]:
graph.addEdge(a[i], a[i + 1])
swap(a[i], a[i + 1])
swapped = true
until not swapped
return graph
函数的输入为长度为n的排列a[]，输出为一张n个节点的无向图。函数中，
emptyGraph()创造了一张空的无向图，addEdge(x, y)向图中添加了一条 x
和 y 之间的无向边，最后返回的 graph 即产生的无向图。
图的点独立集为图中节点集合的一个子集。如果集合S是图G的点独立集，
那么S中任意两个节点在图G中都没有边直接相连。
给定1~n的一个排列， 请求出按照伪代码生成的无向图的最大点独立集的大
小，以及一定会存在于最大点独立集中的节点。
输入格式:
输入第一行包含一个整数n。接下来一行包含?个空格分隔的整数，代表序
列a[]。
输出格式:
输出两行。 第一行包含一个整数， 代表生成的无向图的最大点独立集的大小。
第二行输出最大点独立集中一定会包含的节点在输入序列中对应的下标， 按照从小到大的顺序输出，以空格分隔。
样例输入:
3
3 1 2
样例输出:
2
2 3
数据规模和约定:
据规模和约定】
对于30%的数据，n≤16
对于60%的数据，n≤1000。
对于100%的数据，1≤n≤100,000。
提示：
一定存在于最大点独立集中的节点数未必等于最大点独立集的大小。
思路：
第一问：根据题目中的伪代码，一个点一定会与位于这个点之后并且不大于这个点的点连一条边，样例中3会与1和2连一条边，而1就不会与2连边，这样就构成了一个下降的序列。那么反过来，不连边的点就构成了上升序列，这就是一个点独立集，最大的点独立集就是最长上升子序列。所以第一问的答案就是最长上升子序列的长度。
第二问：问哪些点一定在最长上升子序列中，因为最长上升子序列可能有多个，那么所有上升子序列中公共的点就是一定在最大点独立集中的点。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,tot,a[maxn],f[maxn],c[maxn],sum[maxn],maxx[maxn];
bool p[maxn];
int main()
{
freopen("bubble.in","r",stdin);
freopen("bubble.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
if(a[i]>c[tot])
{
c[++tot]=a[i];
f[i]=tot;
}
else
{
int pos=upper_bound(c+1,c+tot+1,a[i])-c;
c[pos]=a[i];f[i]=pos;
}
}
printf("%d
",tot);
for(int i=n;i>=1;i--)
{
if(f[i]==tot||maxx[f[i]+1]>a[i])
{
p[i]=1;sum[f[i]]++;
maxx[f[i]]=max(maxx[f[i]],a[i]);
}
}
for(int i=1;i<=n;i++)
if(p[i]&&sum[f[i]]==1)
printf("%d ",i);
fclose(stdin);fclose(stdout);
return 0;
}