久违的写篇博客吧
A. Maximum Square
题目链接：https://codeforces.com/contest/1243/problem/A
题意：
给定n个栅栏，对这n个栅栏进行任意排序，问可形成的最大正方形面积是多少
分析：
水题。
先排个序 ， 然后暴力枚举正方形边长就可以了
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l, m, lrt
#define rson m+1, r, rrt
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-;isdigit(ch=getchar());res=(res<<)+(res<<)+ch - );flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=,v=a;while(b){if(b&){r+=v;if(r>p)r-=p;}v<<=;if(v>p)v-=p;b>>=;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=,v=a%p;while(b){if(b&)r=mult(r,v,p);v=mult(v,v,p);b>>=;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=;i<=t;i++){r=mult(r,r,n);if(r==&&z!=&&z!=n-)return true;z=r;}return r!=;}
bool Miller_Rabin(ll n)
{if(n<)return false;if(n==)return true;if(!(n&))return false;ll x=n-,t=;while(!(x&)){x>>=;t++;}srand(time(NULL));
ll o=;for(ll i=;i<o;i++){ll a=rand()%(n-)+;if(CH(a,n,x,t))return false;}return true;}
int prime[],minprime[];
void euler(int n)
{int c=,i,j;for(i=;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==)break;}}} const int N = 1e3 + ;
int a[N];
int main(){
ios;
int t;
cin >> t;
while(t -- )
{
int n;
cin >> n;
int a[N];
rep(i , , n - )
{
cin >> a[i];
}
sort(a,a+n);
int len = ;
per(i , n - , )
{
if(a[i] > len){
len ++;
}
else
{
break;
}
}
cout << len << '\n';
}
return ;
}
B1. Character Swap (Easy Version)
题目链接：https://codeforces.com/contest/1243/problem/B1
题意：
给你两个长度为 n 的字符串 S 和 T ，每次操作你可以交换 S 、T上任意两个位置的字符。问是否能只进行一次操作使 S 串 等于 T串。能输出 "Yes" ， 不能输出 "No"
分析：
遍历字符串，当 S[i] != T[i] 时，判断从i + 1 到 n是否有s[j] == s[i] && t[j] != s[j]，若不存在则说明无法进行一次操作使得两个字符串相等;
若存在则标记cot为0，继续遍历，倘若又一次出现s[i] != t[i]，则输出"No".
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l, m, lrt
#define rson m+1, r, rrt
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-;isdigit(ch=getchar());res=(res<<)+(res<<)+ch - );flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=,v=a;while(b){if(b&){r+=v;if(r>p)r-=p;}v<<=;if(v>p)v-=p;b>>=;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=,v=a%p;while(b){if(b&)r=mult(r,v,p);v=mult(v,v,p);b>>=;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=;i<=t;i++){r=mult(r,r,n);if(r==&&z!=&&z!=n-)return true;z=r;}return r!=;}
bool Miller_Rabin(ll n)
{if(n<)return false;if(n==)return true;if(!(n&))return false;ll x=n-,t=;while(!(x&)){x>>=;t++;}srand(time(NULL));
ll o=;for(ll i=;i<o;i++){ll a=rand()%(n-)+;if(CH(a,n,x,t))return false;}return true;}
int prime[],minprime[];
void euler(int n)
{int c=,i,j;for(i=;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==)break;}}} const int N = 2e5 + ;
char s[N] , t[N];
int main()
{
ios;
int q;
cin >> q;
while(q --)
{
int n ;
cin >> n;
cin >> s + >> t + ;
int flag = , cot = ;
rep(i , , n)
{
if(!flag) break;
if(s[i] == t[i])
continue;
else
{
if(cot == )
{
cout << "No\n";
flag = ;
break;
}
int have = ;
rep(j , i + , n)
{
if(s[j] == s[i] && t[j] != s[j])
{
swap(t[i] , s[j]);
cot = ;
have = ;
}
}
if(!have)
{
cout << "No\n";
flag = ;
}
}
}
if(flag)
cout <<"Yes\n";
}
return ;
}
B2. Character Swap (Hard Version)
题目链接：https://codeforces.com/contest/1243/problem/B2
题意：
给你两个长度为 n 的字符串 S 和 T ，每次操作你可以交换 S 、T上任意两个位置的字符。
问在 2n 操作次数内能否是 S 等于 T，若可以则输出"Yes"并打印交换方法，若不可以则输出"No"
分析：
其实仔细观察我们会发现只要能够使S串变为T串，那么它的操作次数一定是在2n以内。
然而我们还是要优先选择优质的交换方法。
当 S[i] != T[i] 从后遍历判断是否存在S[j] == S[i] , 若存在则交换 T[i] 和 S[j] , 否则判断是否存在T[j] == S[i] ，若存在则可以先交换S[i] 和 T[i] ，再交换S[i] = T[j]，若不存在则输出"No"
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l, m, lrt
#define rson m+1, r, rrt
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-;isdigit(ch=getchar());res=(res<<)+(res<<)+ch - );flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=,v=a;while(b){if(b&){r+=v;if(r>p)r-=p;}v<<=;if(v>p)v-=p;b>>=;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=,v=a%p;while(b){if(b&)r=mult(r,v,p);v=mult(v,v,p);b>>=;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=;i<=t;i++){r=mult(r,r,n);if(r==&&z!=&&z!=n-)return true;z=r;}return r!=;}
bool Miller_Rabin(ll n)
{if(n<)return false;if(n==)return true;if(!(n&))return false;ll x=n-,t=;while(!(x&)){x>>=;t++;}srand(time(NULL));
ll o=;for(ll i=;i<o;i++){ll a=rand()%(n-)+;if(CH(a,n,x,t))return false;}return true;}
int prime[],minprime[];
void euler(int n)
{int c=,i,j;for(i=;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==)break;}}} const int N = 2e5 + ;
char s[N] , t[N];
pair<int , int>hehe;
vector<pair<int , int>>vec;
map<char ,int >haha;
int main()
{
ios;
int T;
cin >> T;
while(T -- )
{
haha.clear();
vec.clear();
int n;
cin >> n;
cin >> s + >> t + ; rep(i , , n)
haha[s[i]] ++ , haha[t[i]] ++ ;
int flag = ;
rep(i , , )
{
if(haha[i + 'a'] & )
{
flag = ;
break;
}
}
if(flag)
{
cout << "No" << '\n';
continue;
}
rep(i , , n)
{
if(s[i] == t[i])
continue;
else
{
int falg = ;
rep(j , i + , n)
{
if(s[i] == s[j])
{
hehe.first = j , hehe.second = i;
vec.pb(hehe);
swap(s[j] , t[i]);
falg = ;
break;
}
}
if(!falg)
{
rep(j , i + , n)
{
if(s[i] == t[j])
{
swap(s[i] , t[i]);
hehe.fi = i , hehe.se = i;
vec.pb(hehe);
swap(s[i] , t[j]);
hehe.fi = i , hehe.se = j;
vec.pb(hehe);
break;
}
}
}
}
}
int len = vec.size();
if(len >= * n)
{
cout << "No" << '\n';
continue;
}
cout << "Yes" << '\n';
cout << vec.size() << '\n';
rep(i , , vec.size() - )
cout << vec[i].fi << " " << vec[i].se << '\n';
}
return ;
}
C. Tile Painting
题目链接：https://codeforces.com/contest/1243/problem/C
题意：
给你 n 个方格 ， 第 i 个位置的倍数的颜色需要和 第 i 个位置的颜色相同，问你最多可以用多少种颜色来填充
分析：
找找规律我们会发现它是有循环节的，而循环节就是n / lcm = 所有因子的gcd
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l, m, lrt
#define rson m+1, r, rrt
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-;isdigit(ch=getchar());res=(res<<)+(res<<)+ch - );flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=,v=a;while(b){if(b&){r+=v;if(r>p)r-=p;}v<<=;if(v>p)v-=p;b>>=;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=,v=a%p;while(b){if(b&)r=mult(r,v,p);v=mult(v,v,p);b>>=;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=;i<=t;i++){r=mult(r,r,n);if(r==&&z!=&&z!=n-)return true;z=r;}return r!=;}
bool Miller_Rabin(ll n)
{if(n<)return false;if(n==)return true;if(!(n&))return false;ll x=n-,t=;while(!(x&)){x>>=;t++;}srand(time(NULL));
ll o=;for(ll i=;i<o;i++){ll a=rand()%(n-)+;if(CH(a,n,x,t))return false;}return true;}
int prime[],minprime[];
void euler(int n)
{int c=,i,j;for(i=;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==)break;}}} const int N = 2e5 + ;
vector<ll>haha;
void init(ll n)
{
ll i ;
for(i = ; i * i < n ; i ++)
{
if(n % i == )
haha.pb(i) , haha.pb(n / i);
}
if(i * i == n)
haha.pb(i);
}
int main()
{
ios;
haha.clear();
ll n;
cin >> n;
init(n);
haha.pb(n);
ll ans = haha[];
rep(i , , haha.size() - )
ans = gcd(ans , haha[i]);
cout << ans << '\n';
return ;
}
D. 0-1 MST
题目链接：https://codeforces.com/contest/1243/problem/D
题意：
给你一张包含 n 个点的完全图，其中有m条边的权值为1，其它的为0。现要求你求出最小生成树的权值
分析：
先将 n 个点存入 set<int> S（表示该点还未在任何连通块里），并用vis进行标记
再对每个点开个set<int>G用来存图
遍历每个点 ， 若 vis[i] = 1 则将 i 从集合S中删除并以 i 为起点进行 bfs 寻找连通块 ， 同时连通块个数 cnt ++。
bfs 过程中遍历S , 若 G[i].count(*it) == 1 ， 则说明两点没有连通 ， 若为 0 则说明两点有连通。若连通则将其从S中erase、vis标记为1，并加入队列进行下一轮bfs
最后输出 cnt - 1即可
#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define MOD 1000000007
#define pi 3.14159265358979323
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l, m, lrt
#define rson m+1, r, rrt
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int inf (0x3f3f3f3f);
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-;isdigit(ch=getchar());res=(res<<)+(res<<)+ch - );flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}
ll mult(ll a,ll b,ll p){a%=p;b%=p;ll r=,v=a;while(b){if(b&){r+=v;if(r>p)r-=p;}v<<=;if(v>p)v-=p;b>>=;}return r;}
ll quick_pow(ll a,ll b,ll p){ll r=,v=a%p;while(b){if(b&)r=mult(r,v,p);v=mult(v,v,p);b>>=;}return r;}
bool CH(ll a,ll n,ll x,ll t)
{ll r=quick_pow(a,x,n);ll z=r;for(ll i=;i<=t;i++){r=mult(r,r,n);if(r==&&z!=&&z!=n-)return true;z=r;}return r!=;}
bool Miller_Rabin(ll n)
{if(n<)return false;if(n==)return true;if(!(n&))return false;ll x=n-,t=;while(!(x&)){x>>=;t++;}srand(time(NULL));
ll o=;for(ll i=;i<o;i++){ll a=rand()%(n-)+;if(CH(a,n,x,t))return false;}return true;}
int prime[],minprime[];
void euler(int n)
{int c=,i,j;for(i=;i<=n;i++){if(!minprime[i])prime[++c]=i,minprime[i]=i;for(j=;j<=c&&i*prime[j]<=n;j++)
{minprime[i*prime[j]]=prime[j];if(i%prime[j]==)break;}}} const int N = 2e5 + ;
set<int>G[N];
set<int>s;
set<int>::iterator it;
int n , m;
int vis[N];
void bfs(int x)
{
queue<int>q;
q.push(x);
s.erase(x);
vis[x] = ;
while(!q.empty())
{
int k = q.front();
q.pop();
for(it = s.begin() ; it != s.end() ;)
{
int ha = *it ++;
if(G[k].count(ha) == )
{
vis[ha] = ;
q.push(ha);
s.erase(ha);
}
}
}
}
int main()
{
ios;
cin >> n >> m;
rep(i , , n)
s.insert(i);
rep(i , , m)
{
int x , y;
cin >> x >> y;
G[x].insert(y);
G[y].insert(x);
}
int ans = ;
rep(i , , n)
{
if(!vis[i])
{
ans ++;
bfs(i);
}
}
cout << ans - << '\n';
return ;
}