建一个app要多少钱/宁德seo培训

Description

给出一个$n$个点$m$条边的无向图，现在要求加最少的边使得该图有一个长度超过$1$的奇环，问最少边数及有多少种方案加最少条边形成奇环

Input

第一行两个整数$n,m$表示点数和边数，之后$m$行每行两个整数$u,v$表示一条无向边$(3\le n\le 10^5,0\le m\le min(\frac{n(n-1)}{2},10^5))$

Output

输出所加最少边数$t$以及加$t$条边有多少种方案可以形成奇环

Sample Input

4 4
1 2
1 3
4 2
4 3

Sample Output

1 2

Solution

若没边则至少需要加三条边才能形成三元环，方案数$C_n^3$

若已经存在奇环，则不需要加边，方案数为$1$

若不存在奇环，且每个连通块点数不超过$2$，那么对于每一条边，只有从其他$n-2$个点选一个点与这条边的两个端点连边可形才成三元环，需要加两条边，方案数$(n-2)\cdot m$

若不存在奇环，且存在点数超过$2$的连通块，对每个连通块黑白染色后，假设白点$x$个，黑点$y$个，由于$x+y>2$，那么必然有$x>1$或$y>1$，故对于每个点数超过$2$的连通块，可以从一个颜色的点中选出两个连一条边即可形成奇环，需要加一条边，方案数$C_x^2+C_y^2$

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=100005;
int n,m,c[maxn],num[3],res,flag;
vector<int>g[maxn];
void dfs(int u,int col)
{if(flag)return ;c[u]=col;num[col]++;res++;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(c[v]==-1)dfs(v,col^1);else if(c[v]==c[u]){flag=1;return ;}}
}
int main()
{while(~scanf("%d%d",&n,&m)){if(m==0){printf("3 %I64d\n",(ll)n*(n-1)*(n-2)/6);continue;}for(int i=1;i<=n;i++)g[i].clear();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v),g[v].push_back(u);}memset(c,-1,sizeof(c));ll ans=0;int mx=0;flag=0;for(int i=1;i<=n;i++)if(c[i]==-1){res=num[0]=num[1]=0;dfs(i,0);if(flag)break;mx=max(mx,res);ans+=(ll)num[0]*(num[0]-1)/2+(ll)num[1]*(num[1]-1)/2;}if(flag)printf("0 1\n");else if(mx<=2)printf("2 %I64d\n",(ll)(n-2)*m);else printf("1 %I64d\n",ans);}return 0;
}