0%

我的ACM模版

字符串处理

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int maxm = 10000 + 10;
const int maxn = 1000000 + 10;
char x[maxm], y[maxn];// x: 模式串 y: 主串
int m, n;//m: len(x) n: len(y)
int Next[maxm];
void kmp_pre(){
int i, j;
j = Next[0] = -1;
i = 0;
while(i < m){
while(-1 != j && x[i] != x[j]) j = Next[j];
Next[++i] = ++j;
}
}
int KMP_Count(){
int i, j;
int ans = 0;
kmp_pre();
i = j = 0;
while(i < n){
while(-1 != j && y[i] != x[j]) j = Next[j];
i++; j++;
if(j >= m){
ans++;
j = Next[j];
}
}
return ans;
}

e-KMP

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//求最长回文子串
const int MAXN = 110010;
char Ma[MAXN*2];
int Mp[MAXN*2];
void Manacher(char s[], int len){
int l = 0;
Ma[l++] = '$';
Ma[l++] = '#';
for(int i=0; i<len; i++){
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0, id = 0;
for(int i=0; i<l; i++){
Mp[i] = mx>i?min(Mp[2*id-i],mx-i):1;
while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
if(i+Mp[i]>mx){
mx = i + Mp[i];
id = i;
}
}
}
/*
abaaba
i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
Ma[i]: $ # a # b # a # a # b # a #
Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1
*/
char s[MAXN];
int main(){
while(scanf("%s",s)==1){
int len = (int)strlen(s);
Manacher(s, len);
int ans = 0;
for(int i=0; i<2*len+2; i++){
ans = max(ans, Mp[i]-1);
}
printf("%d\n", ans);
}
return 0;
}

Aho-Corasick 自动机

example: HDU 2222: 求目标串中出现了几个模式串

1

区间不同字串个数是模版题,可用 字符串 hash,后缀数组,后缀自动机的任何一个求解。

数学

素数

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
long long mi(long long a,long long b)
{
long long ans=1;
a%=mod;
while (b){
if (b&1)
ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans%mod;
}

快速乘

快速乘法(用于long long的值相乘对p取模,防止相乘溢出,将乘改成加即可)

一般是结合快速幂处理long long的数据使用

1
2
3
4
5
6
7
8
9
#define LL long long
LL multiply(LL x,LL y,LL p){
LL ret=0;
for(;y;y>>=1){
if(y&1) ret=(ret+x)%p;
x=(x+x)%p;
}
return ret;
}

欧拉函数

分解质因数

1
2
3
4
5
6
7
8
9
10
11
vector<int> dec(int n){
vector<int> p;
for(int i=2;i*i<=n;i++){
if(n%i==0){
p.push_back(i);
while(n%i==0) n/=i;
}
}
if(n>1) p.push_back(n);
return p;
}

数据结构

二叉索引树(树状数组)

对一个 n 个元素的数组 $A_1、 A_2、\cdots,A_n$ ,可以执行以下两种操作。

  • Add(x, d)操作:让 $A_x$ 增加 d。
  • Query(L, R):计算 $A_L+A_{L+1}+ \cdots +A_R$ 。

两种操作的时间复杂度都是 $O(logn)$ 。

下面代码用到了辅助数组 C ,具体含义请看刘汝佳蓝书 $P_{195}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define lowbit(x) (x&(-x));
const int maxn = 5e4 + 10;
int C[maxn];
int n;
int sum(int x){
int ret = 0;
while(x > 0){
ret += C[x]; x -= lowbit(x);
}
return ret;
}
void add(int x, int d){
while(x <= n){
C[x] += d; x += lowbit(x);
}
}
/*
A = {1, 2, 3, 4}
Add(2, 10)
Add(3, 2)
Query(1, 4)
*/
// example:
int main(){
n = 4;
memset(C, 0, sizeof C);
for(int i = 1; i <= 4; i++){
add(i, i);//init
}
add(2, 10);
add(3, 2);
printf("%d", sum(4) - sum(0));
return 0;
}

RMQ

解决范围最小值或最大值问题(以最大值为例)

$dp[i][j]$ 表示 从 i 开始的,长度为 $2^j$ 的一段元素的最小值,则可以用递推的方法计算出:
$$
dp[i][j] = max(dp[i][j-1],dp[i+2^{j-1}][j-1])
$$
初始化 $O(nlogn)$ ,查询 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn = 5e4 + 10;
int dp[maxn][20];
int mm[maxn];
// 初始化 RMQ,b[1:n]数组下标从 1 开始,如果从 0 开始简单修改即可
void initRMQ(int n, int b[]){
mm[0] = -1;
for(int i = 1; i <= n; i++){
mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
dp[i][0] = b[i];
}
for(int j = 1; j <= mm[n]; j++){
for(int i = 1; i + (1<<j) - 1 <= n; i++){
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
}
//查询最大值
int rmq(int x, int y){
int k = mm[y-x+1];
return max(dp[x][k], dp[y-(1<<k)+1][k]);
}

主席树

  • 查询区间有多少不同的数
  • 静态区间第 K 大
  • 树上路径点权第 K 大
  • 动态第 K 大

图论

最短路

最小生成树

次小生成树

割点与桥

二分图匹配

搜索

八数码

动态规划

最长上升子序列

背包

计算几何

其他

背包问题

例题hdu1864

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//37-->38行为模板
#include <bits/stdc++.h>
using namespace std;
int dp[3000050];//由于每张发票不超过1000,最多30张,扩大100倍数后开这么大即可
int main() {
char ch;
double x,y;
int sum,a,b,c,money[35],v;
int t,i,j,k;
while(cin>>x>>t&&t) {
sum = (int)(x*100);//将小数化作整数处理
memset(money,0,sizeof(money));
memset(dp,0,sizeof(dp));
int l = 0;
for(i = 0; i<t; i++) {
cin>>k;
a = b = c = 0;
int flag = 1;
while(k--) {
scanf(" %c:%lf",&ch,&y);
v = (int)(y*100);
if(ch == 'A' && a+v<=60000)
a+=v;
else if(ch == 'B' && b+v<=60000)
b+=v;
else if(ch == 'C' && c+v<=60000)
c+=v;
else
flag = 0;
}
if(a+b+c<=100000 && a<=60000 && b<=60000 && c<=60000 && flag)//按题意所说,必须满足这些条件
money[l++] = a+b+c;
}
for(i = 0; i<=l; i++) {
for(j = sum; j>=money[i]; j--)
dp[j] = max(dp[j],dp[j-money[i]]+money[i]);
}
cout<<fixed<<setprecision(2)<<(double)dp[sum]/100<<endl;
}

return 0;
}

扩展kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int maxn=100010;   //字符串长度最大值
int next[maxn],ex[maxn]; //ex数组即为extend数组
//预处理计算next数组
void GETNEXT(char *str)
{
int i=0,j,po,len=strlen(str);
next[0]=len;//初始化next[0]
while(str[i]==str[i+1]&&i+1<len)//计算next[1]
i++;
next[1]=i;
po=1;//初始化po的位置
for(i=2;i<len;i++)
{
if(next[i-po]+i<next[po]+po)//第一种情况,可以直接得到next[i]的值
next[i]=next[i-po];
else//第二种情况,要继续匹配才能得到next[i]的值
{
j=next[po]+po-i;
if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
while(i+j<len&&str[j]==str[j+i])//计算next[i]
j++;
next[i]=j;
po=i;//更新po的位置
}
}
}
//计算extend数组
void EXKMP(char *s1,char *s2)
{
int i=0,j,po,len=strlen(s1),l2=strlen(s2);
GETNEXT(s2);//计算子串的next数组
while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0]
i++;
ex[0]=i;
po=0;//初始化po的位置
for(i=1;i<len;i++)
{
if(next[i-po]+i<ex[po]+po)//第一种情况,直接可以得到ex[i]的值
ex[i]=next[i-po];
else//第二种情况,要继续匹配才能得到ex[i]的值
{
j=ex[po]+po-i;
if(j<0)j=0;//如果i>ex[po]+po则要从头开始匹配
while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算ex[i]
j++;
ex[i]=j;
po=i;//更新po的位置
}
}
}


树状数组

(主要是了解lowbit(x&(-x)),设计树状数组的为了方便数组下标一般从1开始)

例题hdu1166

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=50005;
int n;
int arr[maxn];///存储从0001开始
void add(int p,int x)
{
while(p<=n)
{
arr[p]+=x;
p+=(p&(-p));
}
}
int sum(int p)
{
int ans=0;
while(p>0)
{
ans+=arr[p];
p-=(p&(-p));
}
return ans;
}
int main()
{
int t;
cin>>t;
int lcount=0;
string s;
while(t--)
{
memset(arr,0,sizeof arr);
cout<<"Case "<<++lcount<<":"<<endl;
cin>>n;
int num;
for(int i=1; i<=n; i++)
{
cin>>num;
add(i,num);
}
int i,j;
while(cin>>s&&s!="End")
{
cin>>i>>j;
if(s=="Add")
add(i,j);
else if(s=="Sub")
add(i,-j);
else if(s=="Query")
cout<<sum(j)-sum(i-1)<<endl;

}

}
}

排列组合Cnm

例题:UVA 12034 Race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
using namespace std;

const int N=1005;
const int mod=10056;
int f[N],c[N][N];

void init()
{
int i,j;
c[1][0]=c[1][1]=1;
for (i=2; i<N; i++)
{
c[i][0]=1;
for (j=1; j<=i/2; j++)
c[i][j]=c[i][i-j]=(c[i-1][j-1]+c[i-1][j])%mod;//求Cnm
}
//f[1]=1;
for (i=1; i<N; i++)//第一名有i个人
{
f[i]=1;
for (j=1; j<i; j++)
{
f[i]+=c[i][j]*f[i-j];//f(n)=∑C(n,i)f(n-i)
f[i]%=mod;
}
}
}

int main()
{
int t,n,lcount=0;
init();
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
printf("Case %d: %d\n",++lcount,f[n]);

}
}

求最大公因数和最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int gcd(int a,int b)///最大公因数,测试数据1e8,没有C++自带的__gcd(,)函数快
{
return (a%b==0)?b:gcd(b,a%b);
}
int lcm(int a,int b)///最小公倍数
{
return (a*b/gcd(a,b));
}
int main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl<<lcm(a,b)<<endl;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
long long mi(long long a,long long b)
{
long long ans=1;
a%=mod;
while (b)
{
if (b&1)
ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans%mod;
}

快速乘

快速乘法(用于long long的值相乘对p取模,防止相乘溢出,将乘改成加即可)

一般是结合快速幂处理long long的数据使用

1
2
3
4
5
6
7
8
9
10
#define LL long long
LL multiply(LL x,LL y,LL p){
LL ret=0;
for(;y;y>>=1){
if(y&1) ret=(ret+x)%p;
x=(x+x)%p;
}
return ret;
}

最短路

Dijkstra:无堆优化版,复杂度$O(N^2)$

Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int maxn=2500+10;
const int inf=0x3f3f3f3f;//设置你认为的最长的边
int e[maxn][maxn];
int dis[maxn];
int book[maxn];
int T,C,Ts,Te;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T>>C>>Ts>>Te;//T个城镇,C条路,起点Ts,终点Te,,,,无向图
//初始化边
for(int i=1;i<=T;i++){
for(int j=1;j<=T;j++){
e[i][j]=e[j][i]=(i==j?0:inf);
}
}
//输入边的数据
for(int i=0;i<C;i++){
int a,b,c;
cin>>a>>b>>c;
if(c<e[a][b]) e[a][b]=e[b][a]=c;//考虑重边
}
//初始化起点的dis数组
for(int i=1;i<=T;i++){
dis[i]=e[Ts][i];
}
//初始化已知最短路程的顶点集合(已知的标记为1)
memset(book,0,sizeof book);
book[Ts]=1;
//核心部分
for(int i=1;i<=T-1;i++){
int mi=inf,u;
//找到距离起点Ts最近的顶点
for(int j=1;j<=T;j++){
if(book[j]==0&&dis[j]<mi){
mi=dis[j];
u=j;
}
}
book[u]=1;
for(int v=1;v<=T;v++){
if(e[u][v]<inf&&!vis[v]){//对与u联通并且未被标记的点v进行松弛操作
if(dis[v]>dis[u]+e[u][v]){//松弛操作
dis[v]=dis[u]+e[u][v];
}
}
}

}
cout<<dis[Te];//输出到终点Te的最短路
}

堆优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
* 使用优先队列优化Dijkstra
* 复杂度O(ElogE)
* 注意对vector<Edge>E[max_n]进行初始化后加边
*/
using namespace std;
const int INF=0x3f3f3f3f;
const int max_n=1e3+10;
const int max_m=5e5+10;
int n,m;
struct qnode{
int v;
int c;
qnode(int _v=0,int _c=0):v(_v),c(_c){}
bool operator<(const qnode &r)const{
return c>r.c;
}
};
struct Edge{
int v,cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[max_n];
bool vis[max_n];
int dist[max_n];//起点到各个点的最短距离
//点的编号从1开始
void Dijkstra(int n,int start){
memset(vis,false,sizeof vis);
for(int i=1;i<=n;i++) dist[i]=INF;
priority_queue<qnode>que;
dist[start]=0;
que.push(qnode(start,0));
qnode tmp;
while(!que.empty()){
tmp=que.top();
que.pop();
int u=tmp.v;
if(vis[u]) continue;
vis[u]=true;
for(int i=0;i<E[u].size();i++){
int v=E[u][i].v;
int cost=E[u][i].cost;
if(!vis[v]&&dist[v]>dist[u]+cost){
dist[v]=dist[u]+cost;
que.push(qnode(v,dist[v]));
}
}
}
}
void addedge(int u,int v,int w){
E[u].push_back(Edge(v,w));
E[v].push_back(Edge(u,w));
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
int a,b,c;
while(m--){
cin>>a>>b>>c;
addedge(a,b,c);
}
Dijkstra(n,1);
cout<<dist[n];
return 0;
}

Dijkstra虽好,但是他不能解决带有负边权的图,下面是复杂度$O(NM)$的Bellman-Ford算法

Bellman-Ford算法

1
在这里插入代码片

Trie树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct Trie{
int cnt;//记录以此结点为前缀的单词的个数
Trie* letter[26];//26个字母
Trie(){
cnt=0;
memset(letter,0,sizeof letter);
}
}root;
void insertTrie(string str){
Trie* p=&root;
int len=str.length();
for(int i=0;i<len;i++){
int lett=str[i]-'a';
if(p->letter[lett]==0) p->letter[lett]=new Trie;
p=p->letter[lett];
p->cnt++;
}
}
int Find(string str){
Trie* p=&root;
int len=str.length();
for(int i=0;i<len;i++){
int lett=str[i]-'a';
if(p->letter[lett]==0) return 0;
else p=p->letter[lett];
}
return p->cnt;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
while(t--){
string str;
cin>>str;
insertTrie(str);
}
cin>>t;
while(t--){
string str;
cin>>str;
cout<<Find(str)<<endl;
}
}

求最长回文串

hihocoder 1032

中心扩展法(加了一点优化,时间复杂度 < $O(N^2)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char str[1000005];
int main(){
int n; scanf("%d",&n);
while(n--){
str[0]='#';
scanf("%s",str+1);
int len=strlen(str),tag=0,ans=1;
for(int i=1;str[i];i++){
int s=i,t=i;
while(str[t]==str[t+1]) t++;
i=t;//没有这句会超时,主要是靠这个来优化
while(str[s-1]==str[t+1]) s--,t++;
ans=max(ans,t-s+1);
}
printf("%d\n",ans);
}
}

Manacher算法(马拉车算法),时间复杂度$O(N^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
/*
* 求最长回文子串
*/
const int MAXN = 110010;
char Ma[MAXN*2];
int Mp[MAXN*2];
void Manacher(char s[], int len){
int l = 0;
Ma[l++] = '$';
Ma[l++] = '#';
for(int i=0; i<len; i++){
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0, id = 0;
for(int i=0; i<l; i++){
Mp[i] = mx>i?min(Mp[2*id-i],mx-i):1;
while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
if(i+Mp[i]>mx){
mx = i + Mp[i];
id = i;
}
}
}
/*
abaaba
i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
Ma[i]: $ # a # b # a # a # b # a #
Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1
*/
char s[MAXN];
int main(){
while(scanf("%s",s)==1){
int len = (int)strlen(s);
Manacher(s, len);
int ans = 0;
for(int i=0; i<2*len+2; i++){
ans = max(ans, Mp[i]-1);
}
printf("%d\n", ans);
}
return 0;
}

最长递增子序列

1

JAVA大整数和大小数

  • 大整数是BigInteger
  • 大小数是BigDecimal

当题目对小数精度要求高时,为了方便,可以直接使用BigDecimal,特别方便。

  • 常用操作
    1. 加:add
    2. 减:subtract
    3. 乘:multiply
    4. 除:divide
    5. 取余:remainder

下面是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
DecimalFormat df = new DecimalFormat("0.000");
BigInteger md=BigInteger.TEN;
int t;
while(cin.hasNext()){
t=cin.nextInt();
int cnt=0;
BigDecimal num,pre=new BigDecimal("0.001");
while(t-->0){
num=cin.nextBigDecimal();
BigInteger old=num.multiply(new BigDecimal("1000")).toBigInteger();
int last=old.remainder(md).intValue();//BigInteger->int
cnt+=(last>4?(10-last):-last);
}
System.out.println(df.format(pre.multiply(new BigDecimal(cnt))));
}
cin.close();
}
}

最小割最大流模版

链接🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
struct edge{
LL from,to,cap,flow;
edge(){}
edge(LL from,LL to,LL cap,LL flow):from(from),to(to),cap(cap),flow(flow){}
};
struct dinic{
LL n,m,s,t;
vector<edge> edges;
vector<int > G[maxn];
bool vis[maxn];
LL cur[maxn];
LL d[maxn];

void addedge(LL from,LL to,LL cap){
edges.push_back(edge(from,to,cap,0));
edges.push_back(edge(to,from,0,0));
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}

bool bfs(){
memset(vis,0,sizeof(vis));
queue <int> Q;
Q.push(s);
d[s]=0;
vis[s]=1;
while(!Q.empty()){
LL x=Q.front();
Q.pop();
for(LL i=0;i<G[x].size();i++){
edge &e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
LL dfs(LL x,LL a){
if(x==t||a==0) return a;
LL flow=0;
LL f;
for(LL &i=cur[x];i<G[x].size();i++){
edge &e=edges[G[x][i]];
if((d[e.to]==d[x]+1)&&(f=dfs(e.to,min(e.cap-e.flow,a)))>0){
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}

LL maxflow(LL a,LL b){
s=a;t=b;
LL flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
};

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e3+10;
int n,m,a,b,fa[maxn];
int find(int x){
return (fa[x]==x?x:fa[x]=find(fa[x]));
}
void merge(int a,int b){
a=find(a);b=find(b);
if(a!=b) fa[a]=b;
}
int main(){
while(scanf("%d",&n),n){
scanf("%d",&m);
for(int i=1;i<=n;i++) fa[i]=i;
while(m--){
scanf("%d%d",&a,&b);
merge(a,b);
}
int ans=0;
for(int i=1;i<=n;i++) ans+=(fa[i]==i);
printf("%d\n",ans-1);
}

}

杂谈

  • priority_queue优先队列默认是大顶堆。