题解
往无向图中添加至少几条边,使得图中包含奇数环?
注意是要添加少边,而不是使环小
讨论
1.0条
当且仅当原图中存在奇环,方案数为0
用bfs染色判断,即对于一个环,bfs一定会绕一圈该环,然后黑白染色判断奇偶即可
2.一条
当且仅当存在一连通图大小大于等于3
对于该连通图内,对方案数的贡献为距离为偶数的节点对数,根据黑白染色,也就是相同颜色的节点选取两个
\(C_W^2+C_B^2\)
3.两条
当且仅当最大的连通图大小等于2,由于有m条边,所以有m个大小为2的联通块,只需要任选一个联通块和不属于该联通块的点即可
\((n-2)\cdot m\)
4.三条
联通块大小为1,也就是 \(m=0\)
\(C_n^3\)
code
#include<bits/stdc++.h>
#define ll long long
#define lb long double
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
bool flag=0;
vector<ll> G[200005];
ll color[200005]={0};
ll p1=0,p2=0;
ll dfs(ll now,ll fa,ll val)//dfs染色,子节点颜色和父节点有关
{
color[now]=val;
if(val==1) p1++;
else p2++;
ll sum=1;
for(auto next:G[now])
{
if(next==fa) continue;
if(!color[next])
{
sum+=dfs(next,now,-val);
}
else
{
if(color[next]==color[now])
{
flag=1;
return 1;
}
}
}
return sum;
}
ll C(ll n,ll m)
{
if(n<m) return 0;
ll res=1;
for(ll i=1;i<=m;i++)
{
res=res*(n-i+1LL);
res=res/i;
}
return res;
}
void solve()
{
ll n,m;
cin>>n>>m;
if(m==0)
{
cout<<"3 ";
cout<<C(n,3)<<'\n';
return;
}
for(ll i=1;i<=m;i++)
{
ll x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
ll maxs=2;
ll ans=0;
for(ll i=1;i<=n;i++)
{
if(!color[i])
{
p1=0;
p2=0;
maxs=max(maxs,dfs(i,i,1));
if(flag)
{
cout<<"0 1";
return;
}
if(maxs>=3)
{
//printf("p1:%d p2:%d\n",p1,p2);
ans+=C(p1,2)+C(p2,2);
}
}
}
if(maxs==2)
{
cout<<"2 ";
cout<<(n-2LL)*m<<'\n';
}
else
{
cout<<"1 ";
cout<<ans<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TT=1;
//cin>>TT;
while(TT--) solve();
return 0;
}
标签:p2,p1,color,ll,next,now,Vitaly,Cycle
From: https://www.cnblogs.com/pure4knowledge/p/18337487