汉滨区住房和城乡建设局网站,上海网站推广优化公司,高端网站建设熊掌号,wordpress 书 主题传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一张nnn个点mmm条边的简单图#xff0c;让你找出尽可能多的三元环#xff0c;要求每个三元环都不能共边#xff0c;输出三元环数量和具体是那个。 n,m≤1e5n,m\le1e5n,m≤1e5
思路#xff1a;
其实…传送门 文章目录题意思路题意
给你一张nnn个点mmm条边的简单图让你找出尽可能多的三元环要求每个三元环都不能共边输出三元环数量和具体是那个。
n,m≤1e5n,m\le1e5n,m≤1e5
思路
其实比较容易想到我们直接贪心的去选有可能是最优的。
按照这个思想我们考虑dfsdfsdfs先递归到最深层让后将与其相连的边两两组合之后如果有多出来的边就与他的父亲组合可以知道这样一定是最优的因为每一层都尽可能的都用了最多也就有一个边没有被用到。
注意图不一定连通。
//#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
#includeassert.h
#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].r)1)
#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 N400100,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int d[N];
setintv[N],s[N];
struct Node {int a,b,c;
};
vectorNodeans;
bool st[N];
int fa[N];
int cnt;void dfs(int u) {st[u]true;for(auto x:s[u]) {if(st[x]) continue;fa[x]u;dfs(x);}vectorintnow;int pre-1; now.clear();for(auto x:v[u]) {if(xfa[u]) continue;if(pre-1) prex;else ans.pb({pre,u,x}),now.pb(pre),now.pb(x),pre-1;}for(auto x:now) {v[u].erase(v[u].find(x));v[x].erase(v[x].find(u));}if(pre!-1fa[u]) {ans.pb({fa[u],u,pre});v[fa[u]].erase(u);v[u].erase(fa[u]);v[u].erase(pre);v[pre].erase(u);}}int main() {scanf(%d%d,n,m);for(int i1;im;i) {int a,b; scanf(%d%d,a,b);v[a].insert(b); v[b].insert(a);s[a].insert(b); s[b].insert(a);}for(int i1;in;i) if(!st[i]) {dfs(i);}printf(%d\n,ans.size());for(auto x:ans) printf(%d %d %d\n,x.a,x.b,x.c);return 0;
}
