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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const int mod=2e3;
const int Max=2e5+5;
vector<int>mp[Max];
int color[Max],pa[Max],dfn[Max];
bool flag;
int n,m,k,minlen,pos;
/*
void dfs_color(int now,int per,int cl){
color[now]=cl;
for(auto i:mp[now]){
if(!color[i])dfs_color(i,now,3-cl);
else if(color[i]+color[now]!=3){
flag=0;
return ;
}
}
}
*/
///黑白染色dfs
void dfs_color(int now,int per){
for(auto i:mp[now]){
if(i==per)continue;
int temp=3-color[now];
//cout<<now<<" "<<i<<" "<<temp<<endl;
if(!color[i]){
color[i]=temp;
dfs_color(i,now);
}
else if(color[i]+color[now]!=3){
flag=0;
return ;
}
}
}
//找最小环dfs
void dfs_dfn(int now,int per){
pa[now]=per;
///额外记录一个指向父节点的数组用于路径还原
///因为dfn被标记过一次的点不会再被深搜 所以pa[]的值是唯一对应的
for(auto i:mp[now]){
if(i==per)continue;
if(dfn[i]){
if(dfn[now]-dfn[i]>0&&dfn[now]-dfn[i]+1<minlen){
minlen=dfn[now]-dfn[i]+1;
pos=now;
}
}
else {
dfn[i]=dfn[now]+1;
dfs_dfn(i,now);
}
}
}
int main(){
Turnoff;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)color[i]=0,dfn[i]=0,pa[i]=0;
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
}
color[1]=1,minlen=n+1;
dfn[1]=1,dfs_dfn(1,0);
int need=(k+1)>>1;
if(minlen!=n+1){
if(minlen<=k){
cout<<2<<endl;
cout<<minlen<<endl;
while(minlen--){
cout<<pos<<" ";
pos=pa[pos];
}
}
else{
cout<<1<<endl;
while(need--){
cout<<pos<<" ";
pos=pa[pos];
pos=pa[pos];
}
}
cout<<endl;
}
else{
dfs_color(1,0);int cnt=0;
cout<<1<<endl;
for(int i=1;i<=n;i++)if(color[i]==1)cnt++;
if(cnt>=need){
for(int i=1;i<=n&&need;i++){
if(color[i]==1){
need--;
cout<<i<<" ";
}
}
}
else {
for(int i=1;i<=n&&need;i++){
if(color[i]==2){
cout<<i<<" ";
need--;
}
}
}
cout<<endl;
}
}
|