NBUT 1508 火烧赤壁2 - c++编程基础

分析：由于这题N、M、T数据都非常大、于是我们要想办法优化一下、首先要离线、然后逆序查询、这样就不用每次重新构图、只需要每次把当前点的相关边、并入集合中、看连通块有多少、由于内存的限制、所以需要选择合理的存储结构、于是邻接表是必然的、具体见代码：

#include  
#include  
#include  
using namespace std;  
const int maxn=200005;//题目要求数据  
int mpt[maxn];//用于并查集  
int num[maxn];//用于离线记录数据  
int ans[maxn];//用于保存答案  
int vis[maxn];//用于标记是否在集合中  
int n,m,temp;//N个点、M条边、temp表示答案的变量  
struct node{  
    int to,next;//用于临界表存储  
}map[maxn*2];  
int head[maxn];  
int k;//临界表索引  
void add(int x,int y){//邻接表添加边  
    k++;  
    map[k].to=y;  
    map[k].next=head[x];  
    head[x]=k;  
}  
void init(){//初始化并查集  
    for(int i=0;i




=1;i--){//循环test次  
            int now=num[i];  
            vis[now]=0;  
            for(int j=head[now];j!=-1;j=map[j].next){//找相邻的边  
                int s=map[j].to;  
                if(vis[s]==0){//若相邻的边在图上、则合并  
                    merge(now,s);  
                    vis[now]=0;  
                }  
            }  
            ans[i]=temp;//记录当前答案  
            temp++;  
        }  
        for(int i=1;i<=test+1;i++)//输出答案  
            printf("%d\n",ans[i]);  
    }  
    return 0;  
}