题目链接:https://codeforces.com/contest/557/problem/D

题意:给出n个点,m条边无重边,无自环的无向图。问最少加几条边可以找到一个奇环,并且求出加最少边数的方案数。

思路:最少的奇环当然是3个点,3条边构成的奇环了。

显然加最少的边数就是0,1,2,3其中一个。

1.当边数0时,最少加边数为3,方案数就是n个点取3个连环( c(3,n)=n*(n-1)*(n-2)/2/3)

2.当每个点最多有一条边时,最少加边数为2,方案数  边数*(n-2)

3.因为二分图一定不含奇环的,判断是否是二分图,不是二分图,则一定有奇环,最少加边数就是0,方案数自然为1。

4.当为二分图时,最少加边数为1, 染色判断二分图后,同种颜色的点连边会构成奇环,所以方案数就 是颜色相同点 连边  方案数

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
ll n,m;
vector<int> ve[maxn];
int nume[maxn],nump[maxn],sump[maxn];
//nume[i]i点出度,nump[i]第i个连通图白点个数,sump[i]第i个连通图总点数 
int color[maxn];

bool dfs(int x,int c,int scc)//判断是否是二分图,并存储每个连通图的点数和白点的个数 
{
    sump[scc]++;
    color[x]=c;
    if(color[x]==1)
        nump[scc]++;
    int s=ve[x].size();
    for(int i=0;i<s;i++)
    {
        if(color[ve[x][i]]==c)
            return false;
        if(color[ve[x][i]]==0&&!dfs(ve[x][i],-c,scc))
            return false;
    }
    return true;
}

int main()
{
    int u,v;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        ve[u].push_back(v);
        ve[v].push_back(u);
        nume[u]++;//出度,用于下面就算是否只连一条边 
        nume[v]++;
    }
    if(m==0)//1.边数为0时 
    {
        printf("3 %lld\n",n*(n-1)*(n-2)/3/2);
        return 0;
    }
    ll cnt=0;//计算每个点只有一条边的数量,也起到标记作用 
    for(int i=1;i<=n;i++)
    {
        if(nume[i]>1)//不是每个点只有一条边  
        {
            cnt=-1;
            break;
        }
        else if(nume[i]==1)
            cnt++;
    }
    if(cnt!=-1)//2.每个点最多有一条边时
    {
        printf("2 %lld\n",cnt/2*(n-2));
        return 0;
    }
    int flag=0,scc=0;//flag标记是否是二分图,scc计算连通图的个数 
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1,scc++))//不是二分图,有奇环 
            {
                flag=1;
                break;
            }
        }
    }
    if(flag)//3.//不是二分图,有奇环
        printf("0 1\n");
    else//是二分图 
    {
        ll ans=0;
        for(int i=0;i<scc;i++)//对于每个连通块,方案数+=白点选2个+黑点选2个 
            ans+=(ll)nump[i]*(nump[i]-1)/2+(ll)(sump[i]-nump[i])*(sump[i]-nump[i]-1)/2;
        printf("1 %lld\n",ans);
    }
    return 0;
}
12-17 10:18