[原创]Codeforces 557D - Vitaly and Cycle [二分图染色]【图论】

2017-06-21 23:51:59 Tabris_ 阅读数：219

博客爬取于2020-06-14 22:39:57
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/73556860

题目链接:http://codeforces.com/problemset/problem/557/D
——————————————————————————————————————
D. Vitaly and Cycle
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
After Vitaly was expelled from the university, he became interested in the graph theory.

Vitaly especially liked the cycles of an odd length in which each vertex occurs at most once.

Vitaly was wondering how to solve the following problem. You are given an undirected graph consisting of n vertices and m edges, not necessarily connected, without parallel edges and loops. You need to find t — the minimum number of edges that must be added to the given graph in order to form a simple cycle of an odd length, consisting of more than one vertex. Moreover, he must find w — the number of ways to add t edges in order to form a cycle of an odd length (consisting of more than one vertex). It is prohibited to add loops or parallel edges.

Two ways to add edges to the graph are considered equal if they have the same sets of added edges.

Since Vitaly does not study at the university, he asked you to help him with this task.

Input
The first line of the input contains two integers n and m ( — the number of vertices in the graph and the number of edges in the graph.

Next m lines contain the descriptions of the edges of the graph, one edge per line. Each edge is given by a pair of integers ai, bi (1 ≤ ai, bi ≤ n) — the vertices that are connected by the i-th edge. All numbers in the lines are separated by a single space.

It is guaranteed that the given graph doesn’t contain any loops and parallel edges. The graph isn’t necessarily connected.

Output
Print in the first line of the output two space-separated integers t and w — the minimum number of edges that should be added to the graph to form a simple cycle of an odd length consisting of more than one vertex where each vertex occurs at most once, and the number of ways to do this.

Examples
input
4 4
1 2
1 3
4 2
4 3
output
1 2
input
3 3
1 2
2 3
3 1
output
0 1
input
3 0
output
3 1
Note
The simple cycle is a cycle that doesn’t contain any vertex twice.
——————————————————————————————————————
题目大意：
就是现在一个N个节点，M条边的无向图，问你最少添加多少条边，能找到一个奇圈，添加的方法有多少个

解题思路：

判断奇圈偶圈，很容易想到二分图染色，那么通过二分图染色，就能确定很多信息了，

首先能确定的是最多也就添加3条边， 3条边就能将三个点变成一个奇圈了，

那么添加边就是要变成一个3个节点的奇圈

那么就分这四种情况讨论

1.添加0条边
就是原图中有奇圈了， 通过染色判断，方案数就是1了
2.添加1条边
只需添加一条边的时候就是一个点a连向点b,c. 这时候将b,c连上就好了
这种情况需要在一侧的多个节点都能和另一边的节点直接或间接连上才行,
所以我用了一个并查集维护联通性,然后统计个数
3.添加2条边
如果一个节点至多被一条边连着,
那么想要构成奇圈,就要将边的两个端点连上另外的一个一个节点构成奇圈
方案数就是m∗(n−2)m*(n-2)
4.添加3条边
只有一条边都没有的时候才要添加三条边,
方案数就是在n个点取3个节点的方案数

分类讨论即可

附本题代码
——————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1e5+7;

/************************************/
int k,n,m;

int pre[N];

int findi(int x){
    int r=x;
    while(r!=pre[r])r=pre[r];
    for(int i=x,j;r!=i;){
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y){
    int fx=findi(x),fy=findi(y);
    pre[fx]=fy;
}


vector<int >G[N];

int col[N];
//二分图染色  用来判断是不是二分图
int color(int s){
    queue<int>q;int ans =0 ;
    q.push(s);col[s]=1;
    while(!q.empty()){
        int u = q.front();q.pop();
        int gz=G[u].size();
        for(int i=0,to;i<gz;i++){
            to=G[u][i];
            if(col[to]==0){
                col[to]=3-col[u];
                q.push(to);
            }
            else if(col[to]==col[u])
                ans++;
        }
    }
    return ans>>1;
}

void init(){
    for(int i=0;i<=n;i++) G[i].clear(),col[i]=0,pre[i]=i;
}

void add(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u); //无向图才需要
}

int x[N],y[N];

int main(){
    scanf("%d%d",&n,&m);
    init();
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v);join(u,v);
    }

    if(m==0) return 0*printf("3 %lld\n",(LL)n*(n-1)*(n-2)/6);

    int flag=0;
    for(int i=1;i<=n;i++)
        if(col[i]==0) flag+=color(i);

    if(flag) return 0*puts("0 1");

    LL ans = 0;
    flag=0;
    for(int i=1;i<=n;i++){
        if(G[i].size()>1) flag=1;
        if(col[i]==1)ans+=x[findi(i)]++;
        else         ans+=y[findi(i)]++;

    }
    if(flag) printf("1 %lld\n",ans);
    else     printf("2 %lld\n",(LL)m*(n-2));
    return 0;
}