贵阳市建设厅官方网站,官方网站开发需要几个技术人员,苏州网络推广营销公司,网站没询盘怎么做推广传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你个nnn个点mmm条边的图#xff0c;可以选择完成以下两个任务中的一个#xff1a; (1)(1)(1)找出大小恰好为n\sqrt nn的一个独立集。 (2)(2)(2)找出一个长度≥n\ge \sqrt n≥n的一个环。 n≤1e5,m≤…传送门
文章目录题意思路题意
给你个nnn个点mmm条边的图可以选择完成以下两个任务中的一个 (1)(1)(1)找出大小恰好为n\sqrt nn的一个独立集。 (2)(2)(2)找出一个长度≥n\ge \sqrt n≥n的一个环。 n≤1e5,m≤2e5n\le 1e5,m\le 2e5n≤1e5,m≤2e5。
思路
我们构造出一颗dfs树这棵树有一个很重要的性质就是所有非树边链接的两个点都是一个树上的点以及这个点的后代。所以我们可与边建树边找环可以直接用vectorvectorvector存下来这条链上的编号输出的话倒着输出即可。 如果找不到这样的环那么每个点的非树边一定不超过limit−2limit-2limit−2个(limitnlimit\sqrt nlimitn)因为如果limit−2limit-2limit−2的话那么至少存在limit1limit1limit1条非树边那么一定可形成一个大小≥limit\ge limit≥limit的一个环所以得证。 既然非树边一定不超过limit−2limit-2limit−2个那么我们对每个点染色当选了一个点的时候那么与它相邻的点就标记为不选最终一定可选出一个大小正好为n\sqrt nn的独立集。 所以分情况讨论就好啦。
// Problem: F. Ehabs Last Theorem
// Contest: Codeforces - Codeforces Round #628 (Div. 2)
// URL: https://codeforces.com/contest/1325/problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N300010,MN*4,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
vectorintv[N],now,ans;
int depth[N],limit;
bool st[N];void dfs(int u) {now.pb(u);depth[u]now.size();for(auto x:v[u]) {if(!depth[x]) dfs(x);else if(depth[u]-depth[x]limit-1) {printf(2\n);printf(%d\n,depth[u]-depth[x]1);for(int i1;idepth[u]-depth[x]1;i) printf(%d ,now.back()),now.pop_back();puts();exit(0);}}if(!st[u]) {for(auto x:v[u]) st[x]1;ans.pb(u);}now.pop_back();
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);limitsqrt(n);limit(limit*limit!n);while(m--) {int a,b; scanf(%d%d,a,b);v[a].pb(b); v[b].pb(a);}dfs(1);printf(1\n);for(int i0;ians.size()ilimit;i) printf(%d ,ans[i]);puts();return 0;
}
/**/
