题目类型 贪心题
题目意思
给出 3 个数 n, m, v ( 3 <= n <= 1e5, 0 <= m <= 1e5, 1 <= v <= n)
n -> 表示有 n 个点
m -> 表示有 m 条边(无向边)
v -> 表示要删除的点
现在你要在 n 个点上构造 m 条边出来 (注意两点之间只能构造一条无向边, 即没有重边), 这 m 条边构造出来后 n 个点之间要相互可达(即你构造出来的是一个连通图)
然后要求当把点 v 从 n 个点删除后(当然这时候与 v 相连的边也删除了) 剩下的图是不连通的(即某个点没有路通向某个点)
解题方法
首先我们要保证构造出来的 m 条边可以构造出一个连通图, 即 m >= (n-1)
然后可以看到, 既然最终要求剩下的点不连通, 那么我们只要孤立一个点就行了
例如可以这样 -> 孤立的点 u = (v == n ? n-1 : n); 意思是如果 v == n的话我们就孤立 n-1否则就孤立 n
这时可以发现 我们最多可以添加的边数是 除了 u 还有 n-1个点, 每个点向其他的 n-2个点连一条边的话 即有 (n-1)*(n-2)/2 条边(无向边,所以要除2) 然后构造出来的图要连通所以 v -> u要连一条边, 所以 m 最大是 (n-1)*(n-2)/2+1
即如果 (n-1) <= m <= (n-1)*(n-2)/2+1 ,则有解,且很容易就可以构造出来(详见代码)
注意
计算的时候 (n-1)*(n-2)可能会超 int 范围, 所以要用 long long
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int MAXN = 1e2 + 10;
const LL INF = 1LL<<62;
int main() {
LL n, m, v;
while(cin>>n>>m>>v) {
LL tmp = (n-1)*(n-2)/2 + 1;
if(m >= (n-1) && m <= tmp) {
int tk = 1, mark = (v == n ? n-1:n);
cout<<v<<" "<<mark<<endl;
for( int i=1; i<n && tk != m; i++ ) {
for( int j=i+1; j<=n; j++ ) {
if(j == mark) continue;
cout<<i<<" "<<j<<endl;
tk++;
if(tk == m) break;
}
}
}
else printf("-1\n");
}
return 0;
}