A：其实并不是特别难的一个题，想的太复杂了。
首先，我们把关系看成能够传递的，那么我们并查集统计连通块之后。
可以发现，对于一个连通块，最优方案肯定只有1个人会没朋友。
因为一直把和当前删的点有关系的人的人删进去，最后肯定就能删完全部点，并且保证只有第一个进去的人没朋友。
因为要保证字典序最小，我们每次合并并查集的时候，都让大的以小的为父节点，那么最后这个集合的根，肯定就是这个集合里最小的点。
那么我们先把根都扔到小顶堆里，然后在把和堆顶相邻的没删的元素放入，因为小顶堆，会自己保证最小字典序。
// Author: levil #pragma GCC optimize(2) #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<int,int> pii; const int N = 1e6+5; const int M = 1e4; const LL Mod = 998244353; #define rg register #define pi acos(-1) #define INF 1e9 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ /*const int BUF_SIZE = 8e7; inline char nc(){ static char buf[BUF_SIZE],*p1 = buf,*p2 = buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,BUF_SIZE,stdin),p1==p2)?EOF:*p1++; }*///file close. inline int read(){ int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("date1.out","w",stdout);*/} vector<int> G[N]; int fa[N],vis[N]; int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); } int main() { int ca;ca = read(); while(ca--) { int n,m;n = read(),m = read(); for(rg int i = 1;i <= n;++i) G[i].clear(),fa[i] = i,vis[i] = 0; while(m--) { int u,v;u = read(),v = read(); G[u].push_back(v); G[v].push_back(u); int xx = Find(u),yy = Find(v); if(xx > yy) fa[xx] = yy; else fa[yy] = xx; } priority_queue<int,vector<int>,greater<int> > Q; int cnt = 0; for(rg int i = 1;i <= n;++i) if(fa[i] == i) Q.push(i),vis[i] = 1,cnt++; vector<int> ans; while(!Q.empty()) { int u = Q.top(); Q.pop(); ans.push_back(u); for(auto v : G[u]) { if(!vis[v]) vis[v] = 1,Q.push(v); } } printf("%d\n",cnt); for(int i = 0;i < ans.size();++i) printf("%d%c",ans[i],i == ans.size()-1 ? '\n' : ' '); } system("pause"); return 0; }
C：考虑m个点里选择n-1个不同的点，然后除了最大的值外，其他值都能出现两次，那么有出现两次的点有(n-2)种。
那么重复出现的点在左右两边交换的时候，还是不改变。对于出现一次的点(除了最大值)，它在最大值左右两边都是不同的方案。
那么ans = C(m,n-1) * (n-2) * 2^(n-3)
// Author: levil #pragma GCC optimize(2) #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<int,int> pii; const int N = 2e5+5; const int M = 1e4; const LL Mod = 998244353; #define rg register #define pi acos(-1) #define INF 1e9 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ /*const int BUF_SIZE = 8e7; inline char nc(){ static char buf[BUF_SIZE],*p1 = buf,*p2 = buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,BUF_SIZE,stdin),p1==p2)?EOF:*p1++; }*///file close. inline int read(){ int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("date1.out","w",stdout);*/} LL f[N]; void init() { f[0] = 1;for(rg int i = 1;i < N;++i) f[i] = f[i-1]*i%Mod; } LL quick_mi(LL a,LL b) { LL re = 1; while(b) { if(b&1) re = re*a%Mod; a = a*a%Mod; b >>= 1; } return re; } LL inv(LL n){return quick_mi(n,Mod-2);} LL C(LL n,LL m){return f[n]*inv(f[m])%Mod*inv(f[n-m])%Mod;} int main() { init(); int n,m;n = read(),m = read(); if(n <= 2) printf("0\n"); else{ LL ma = C(m,n-1);//m个数里选n-1个不一样的。 LL ans = ma*(n-2)%Mod*quick_mi(2,n-3)%Mod; printf("%lld\n",ans); } // system("pause"); return 0; }