很妙的一题
题意
给出\(n\)个节点\(m\)条边的无向连通图和参数\(k\),求:
- 严格\(\lceil \frac{k}{2} \rceil\)大小的点独立集
- 或大小$ k$的简单环
\(3 \leq k \leq n \leq 10^5,n-1 \leq m \leq 2 \cdot 10^5\)
思路
解法1
我们求出一个原图的DFS树,当某个节点\(u\)存在反向边时,找出终点\(v\)深度最深的反向边.容易看出这个反向边在一个简单环中,且这个简单环不会被其他边分割.如果这个环的大小\(\leq k\),直接输出即可,否则我们取不相邻的\(\lceil \frac{k}{2} \rceil\)个点,它们形成一个点独立集.
如果原图无环(或者说是一棵树),那么我们很容易就能求出大小\(\lceil \frac{k}{2} \rceil\)的点独立集.
解法2
我们求出任意一个环,然后枚举所有的边\(1...m\).如果某条边把这个环分割开(即起点终点都在环上),那么保留这个环的任意一半,继续该过程.最后我们会得到一个不被其他边分割的简单环.之后的处理同解法1.
如果原图是一棵树,同解法1.
(比赛时我用的就是这种做法,但是写T了=-=个人觉得这是最难想也最难写的做法,鬼知道我当时在干什么)
解法3
(来自Um_nik的代码)https://codeforces.com/contest/1364/submission/83636767
%%%%%
根据原题,无论我们求点独立集还是简单环,都需要最多\(k\)个点,那么我们简单粗暴地把所有编号$ > k\(的点删掉,再在剩下的图(**注意新图可能不连通**)中寻找环.如果我们找到任意一个环,直接输出即可,因为这个环的大小肯定\)k\(.如果没有环(新图是一个森林),那也能很容易地找到\) $大小的点独立集.
代码
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
const int maxm = 4e5+10;
struct Edge{
int from,to,next,cnt;
Edge(int from = 0,int to = 0,int next = 0):from(from),to(to),next(next){}
}edge[maxn];
int head[maxn],cnt,d,dep[maxn],p[maxn];
bool vis[maxn],col[maxn];
void addedge(int f,int t){
edge[cnt] = Edge(f,t,head[f]);
head[f] = cnt++;
}
int n,m,k;
void DFS(int u){
if(vis[u])return;
vis[u] = 1;
for(int i = head[u];~i;i = edge[i].next){
int v = edge[i].to;
if(vis[v] and dep[v] > dep[u]){
vector<int>cir = {};
int cur = v;
while(cur != u){
cir.push_back(cur);
cur = p[cur];
}
cir.push_back(u);
int s = cir.size();
cout << 2 << endl << s << endl;
for(int yay:cir)cout << yay << " ";
exit(0);
}
else if(!vis[v]){
p[v] = u;
dep[v] = dep[u]+1;
col[v] = !col[u];
DFS(v);
}
}
}
int main(){
ios::sync_with_stdio(0);
memset(head,-1,sizeof(head));
cin >> n >> m >> k;
d = ceil((double)k/2);
for(int i = 1;i <= m;i++){
int f1,t1;
cin >> f1>> t1;
if(f1 > k or t1 > k)continue;
addedge(f1,t1);
addedge(t1,f1);
}
int cnt1 = 0;
for(int i = 1;i <= n;i++)DFS(i);
vector<int>ans = {};
for(int i = 1;i <= n;i++)if(col[i])cnt1++;
int qwq = 0;
if(cnt1 >= d)qwq = 1;
for(int i = 1;i <= n;i++)if(col[i] == qwq){
if((int)ans.size() == d)break;
ans.push_back(i);
}
cout << 1 << endl;
for(int x:ans)cout << x << " ";
return 0;
}
|