其实我并没有见过原题，只是因为...这被改编成了互测题...
题目中提到了一个序列，这个序列是很重要的，否则这个问题好像是没有合理的时间复杂度解法的
但正因为有了这个序列，这个问题的时间复杂度才让人能够接受
序列的特性：逆序对！
根据题意，我们发现一个图上所有的连边一定来源于这个序列里的逆序对！
那么，如果要求一个点集内部没有连边，内部是不能有逆序对的！
那么这个条件等价于求出这个序列的上升子序列数目！
所以我们记dp[i]表示以i为结尾，获得所求点集的方案数
那么dp[i]就可以由dp[j]进行转移，其中j<i
但并不是所有的j都能转移到i，因为还有第二个约束条件
都要有连边怎么办？
我们发现，首先，如果想用f[j]来更新f[i]，那么j~i之间的点都没有被使用，那这样一来我们就要让他们都与选中的点之间有连边
怎么做？
充要条件：对于任意j<k<i，有a[k]>a[i]或a[k]<a[j]
证明：首先我们知道，由于是上升序列，一定有：a[i]>a[j]
那么，如果要求都有连边，那么k要么会和i构成逆序对，要么会和j以内某个被选中的点构成逆序对
再考虑j以内所有值都比a[j]小，所以如果k能和j以内某个点构成逆序对，必然会和j构成逆序对
即要求：a[k]<a[j]
那么如果k与i构成逆序对，一定要求a[k]>a[i]
于是我们检验上述两个条件就好
可是这样做是O（n^3）过不了啊
再优化一下!
我们能够发现，如果有a[k]>a[i]，根据单调性，一定有a[k]>a[j]！
而a[k]<a[j]的部分是已然成立的
所以我们仅需找出，对于所有a[k]>a[j]的k中最小的a[k]是否大于a[i]即可
而如果我们先枚举j，然后枚举i，那么是可以在枚举i的同时维护出这个最小的a[k]的！
这样时间就降到了O（n^2）
当然，我们忽略了一个问题：序列怎么求？
拓扑排序！
这里的拓扑稍特殊：需要用到优先队列，因为对于没有逆序对的部分，后面的一定比前面的大
最后贴代码：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define mode 1000000007
using namespace std;
int dp[];
int inr[];
int maps[][];
bool used[];
int a[];
int n,m;
int main()
{
freopen("is.in","r",stdin);
freopen("is.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x>y)
{
swap(x,y);
}
inr[y]++;
maps[x][y]=maps[y][x]=;
}
priority_queue <int> M;
for(int i=n;i>=;i--)
{
if(!inr[i])
{
used[i]=;
M.push(i);
}
}
int ttop=n;
while(!M.empty())
{
int u=M.top();
M.pop();
a[u]=ttop--;
for(int i=n;i>=;i--)
{
if(maps[u][i])
{
inr[i]--;
if(!inr[i]&&!used[i])
{
used[i]=;
M.push(i);
}
}
}
}
a[]=,a[n+]=n+;
dp[]=;
for(int j=;j<=n;j++)
{
int minval=n+;
for(int i=j+;i<=n+;i++)
{
if(a[i]<a[j]||a[i]>=minval)
{
continue;
}
dp[i]+=dp[j];
dp[i]%=mode;
minval=a[i];
}
}
printf("%d\n",dp[n+]);
return ;
}