[cf557d]Vitaly and Cycle(黑白染色求奇环)

题目大意：给出一个 n 点 m 边的图，问最少加多少边使其能够存在奇环，加最少边的情况数有多少种。

解题关键：黑白染色求奇环，利用数量分析求解。

奇环：含有奇数个点的环。

二分图不存在奇环。反之亦成立。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<iostream>

#include<cmath>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

const int maxm=1e5+;

int c[maxn];       //color，每个点的黑白属性，-1表示还没有标记，0/1表示黑白,比vis数组多一个作用

ll num[];        //在一次DFS中的黑白点个数

bool f=;          //判断是否出现奇环

int head[maxn],tot,n,m,a,b;

struct edge{

    int to;

    int nxt;

}e[*maxm];

void add_edge(int u,int v){

    e[tot].to=v;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

void init(){

    memset(head,-,sizeof head);

    tot=;

    memset(c,-,sizeof c);

}

void dfs(int u,int x){

    if(f)return;

    c[u]=x;

    num[x]++;

    for(int i=head[u];~i;i=e[i].nxt){

        int j=e[i].to;

        if(c[j]==-) dfs(j,!x);

        else if(c[j]==x){//存在奇环

            f=;

            return;

        }

    }

}

int main(){

    init();

    cin>>n>>m;

    for(int i=;i<=m;i++){

        cin>>a>>b;

        add_edge(a,b);

        add_edge(b,a);

    }

    ll ans=,ans2=;

    if(m==){

        ans=(ll)n*(n-)*(n-)/;

        printf("3 %lld\n",ans);

        return ;

    }

    for(int i=;i<=n&&(!f);i++){

        if(c[i]==-){

            num[]=num[]=;

            dfs(i,);

            ans+=(num[]*(num[]-)+num[]*(num[]-))/;

            if(num[]==&&num[]==){

                ans2+=n-;

            }

        }

    }

    if(f) printf("0 1\n");

    else if(ans) printf("1 %lld\n",ans);

    else printf("2 %lld\n",ans2);

    return ;

}