題面：獨立集中的點一定單調(diào)遞增，支配集外的點不想入集必須保證能與支配集中的每個點都產(chǎn)生逆序?qū)?。所以獨立支配集就是一個不可擴展的嚴(yán)格上升子序列（可擴展元素會被獨立集性質(zhì)強行拉攏）。

所以翻譯一下題面，就是根據(jù)逆序?qū)€原原序列，并且統(tǒng)計原序列中不可擴展的嚴(yán)格上升子序列的個數(shù)。顯然用dp。

1.還原原序列，n^2暴力掃，很好理解。

void?huanyuan?(int?n,int?m){

int?x, y;

????for(int?i = 1; i <= m;i++){

????????scanf("%d%d", &x, &y);

????????in[min(x, y)]++;

????}

????for(int?i = 1; i <= n; i++){

????????for(int?j = 1; j <= n; j++){

????????????if(!vis[j]){

????????????????if(in[i]) in[i]--;

????????????????else{

????????????????????vis[j] = 1;

????????????????????a[i] = j;

????????????????????break;

????????????????}

????????????}

????????}

????}

}

還有一種方法，O(n)的，自己猜的，沒有看到其它題解提到這種方法，但是是對的。

我也不知道怎么解釋正確性。

void?huanyuan(int?n,int?m){

????register?int?x, y;

????for(register?int?i = 1; i <= m;++i){

????????cin>>x>>y;

????????++in[min(x, y)],--in[max(x,y)];

????}

????for(register?int?i = 1; i <= n; ++i){

???? a[i]=i+in[i];

in[i]=0;//注意要初始化in數(shù)組，后面要用

}

}

?

?

?

?

2.?統(tǒng)計原序列中不可擴展的嚴(yán)格上升子序列的個數(shù),n^2復(fù)雜度。

方便理解可以手模樣例。

以樣例三為例：

a[i]: ??2 ?4 ?1 ?5 ?7 ?6 ?3

dp[i]: ?1 ?1 ?1 ?2 ?2 ?2 ?2

in[ i ]: ?1 ?1 ?1 ?1 ?0 ?0 ?0

long?long?solve(){//dp求出無法擴展的單調(diào)遞增子序列的個數(shù)

for(register?int?i=1;i<=n;++i){

????????register?int?Max=0;

????????for(register?int?j=i-1;j>=1;--j){

????????????if(a[i]>a[j]&&a[j]>Max){//如果當(dāng)前a[j]<max肯定被max的數(shù)更新過了

????????????????Max=a[j];

????????????????dp[i]+=dp[j];

????????????????in[j]=1;

????????????}

????????}

????????if(!dp[i])

????????????dp[i]=1;

????}

ans=0;

????for(register?int?i=1;i<=n;++i){

????????//if(!in[i])

????????register?bool?k=in[i]==0;

????????????ans+=dp[i]*k; //只累加沒有被轉(zhuǎn)移過的dp[i]

????}

????return?ans;

}

3.?AC代碼

#include<bits/stdc++.h>

using?namespace?std;

int?n,m,a[1000010],in[1000010],vis[1000010];

long?long?ans,dp[1000010];void?huanyuan(int?n,int?m){

????register?int?x, y;

????for(register?int?i = 1; i <= m;++i){

????????cin>>x>>y;

????????++in[min(x, y)],--in[max(x,y)];

????}

????for(register?int?i = 1; i <= n; ++i){

???? a[i]=i+in[i];

in[i]=0;

}

}long?long?solve(){

for(register?int?i=1;i<=n;++i){

????????int?Max=0;

????????for(register?int?j=i-1;j>=1;--j){

????????????if(a[i]>a[j]&&a[j]>Max){

????????????????Max=a[j];

????????????????dp[i]+=dp[j];

????????????????++in[j];

????????????}

????????}

????????if(!dp[i])

????????????dp[i]=1;

????}

ans=0;

????for(register?int?i=1;i<=n;++i){

????????//if(!in[i])

????????register?bool?k=in[i]==0;

????????????ans+=dp[i]*k;

????}

????return?ans;

}int?main(){

std::ios::sync_with_stdio(false);

???? std::cin.tie(0);

cin>>n>>m;

huanyuan(n,m);

cout<<solve();

return?0;

}

p.s.由于本題數(shù)據(jù)水的離譜，數(shù)組開到1e2就能過。

????? 本蒟蒻第一次寫題解，還請各位龘佬能提提意見。

避雷區(qū)：1.加了cin加速后用scanf會爆0；

2.初始化（比如我代碼中的in數(shù)組在第二個還原算法中需要初始化，優(yōu)化算法的時候出現(xiàn)的問題）