https://codeforc.es/contest/1364/problem/D
看错题了,要求小于等于k的环或者(k+1)/2个独立集
找环dfs树就行了,独立集不知道定理,就盲找了,前十几个数字总有在最大独立集中参与的吧...所以就和1相连的所有点都猜一猜。。。。
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<stack> using namespace std; typedef long long ll; const int maxn = 2e5 + 111; vector<int>G[maxn], ins[maxn]; stack<int>s; void add(int x, int y) { G[x].push_back(y); } int dep[maxn]; int de[maxn]; int n, k, m; int f = 0; int root = 0; int dfs(int x, int fa,int d) { if (f) return 0; if (dep[x]) return 0; dep[x] = d; s.push(x); if (de[x] == 1) root = x; for (int p : G[x]) { if (p == fa || f == 1) continue; if (dep[p]) { int ans = dep[x] - dep[p] + 1; if (ans <= k && f == 0 && ans > 0) { f = 1; cout << 2 << endl; cout << ans << endl; while (s.top() != p && s.size()) { cout << s.top() << " "; s.pop(); } cout << p << " "; cout << endl; return 0; } } else if (dep[p] == 0 && f == 0) { dfs(p, x, d + 1); } } if(s.size()>0) s.pop(); return 0; } int vis[maxn]; int list[maxn]; int jude(int x) { for (int p : G[x]) { if (list[p]) return 0; } return 1; } int dfs2(int x,int f) { if (vis[x]) return 0; vis[x] = 1; if (jude(x)) { ins[f].push_back(x); list[x] = 1; } for (int p : G[x]) { dfs2(p, f); } return 0; } vector<int>cn; int main() { cin >> n >> m >> k; int len = (k + 1) / 2; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; add(x, y); add(y, x); de[x]++; de[y]++; } dfs(1, -1, 1); //memset(vis, 0, sizeof(vis)); if (!f) { for (int i = 1; i <= 10; i++) { cn.push_back(i); for (int p : G[i]) { cn.push_back(p); if (cn.size() >= 10) break; } if (cn.size() >= 10) break; } for (int i = 0; i < cn.size(); i++) { int x = cn[i]; memset(vis, 0, sizeof(vis)); memset(list, 0, sizeof(list)); dfs2(x, i); } int cnt = 0; int len = (k + 1) / 2; cout << 1 << endl; for (int i = 0; i < cn.size(); i++) { if (ins[i].size() >= (k + 1) / 2) { for (int j = 0; j < len; j++){ cout << ins[i][j] << " "; } return 0; } } } return 0; }