3 Steps(二分图)

C - 3 Steps

Time limit : 2sec / Memory limit : 256MB

Score : 500 points

Problem Statement

Rng has a connected undirected graph with N vertices. Currently, there are M edges in the graph, and the i-th edge connects Vertices Ai and Bi.

Rng will add new edges to the graph by repeating the following operation:

Operation: Choose u and v (u≠v) such that Vertex v can be reached by traversing exactly three edges from Vertex u, and add an edge connecting Vertices u and v. It is not allowed to add an edge if there is already an edge connecting Vertices u and v.

Find the maximum possible number of edges that can be added.

Constraints

2≤N≤105
1≤M≤105
1≤Ai,Bi≤N
The graph has no self-loops or multiple edges.
The graph is connected.

Input

Input is given from Standard Input in the following format:

N M

A1 B1

A2 B2

:

AM BM

Output

Find the maximum possible number of edges that can be added.

Sample Input 1

Copy

Sample Output 1

Copy

If we add edges as shown below, four edges can be added, and no more.

Sample Input 2

Copy

Sample Output 2

Copy

Five edges can be added, for example, as follows:

Add an edge connecting Vertex 5 and Vertex 3.
Add an edge connecting Vertex 5 and Vertex 2.
Add an edge connecting Vertex 4 and Vertex 1.
Add an edge connecting Vertex 4 and Vertex 2.
Add an edge connecting Vertex 4 and Vertex 3.

//Atcoder的题目还是有新意啊，可以收获不少

题意： n 个点 m 条边，组成一个无向连通图，重复操作，如果 a 点到 b 点距离为 3 ，并且没有连回 a ，就添加一条 a - b 的边。没有自环，问最多能添加几条边。

分析可知，如有图有奇数环，必然可加成完全图

如果图是二分图，则会变成完全二分图，

否则最终变为完全图

二分图dfs染色即可

 #include <bits/stdc++.h>

 using namespace std;

 # define LL          long long

 # define pr          pair

 # define mkp         make_pair

 # define lowbit(x)   ((x)&(-x))

 # define PI          acos(-1.0)

 # define INF         0x3f3f3f3f3f3f3f3f

 # define eps         1e-

 # define MOD         

 inline int scan() {

     int x=,f=; char ch=getchar();

     while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 inline void Out(int a) {

     if(a<) {putchar('-'); a=-a;}

     if(a>=) Out(a/);

     putchar(a%+'');

 }

 # define MX

 /**************************/

 int n,m;

 vector<int> G[MX];

 int clo[MX];

 bool check()

 {

     bool ok=;

     for (int i=;i<=n;i++)

     {

         if (G[i].size()>=)

         {

             if (ok) return ;

             ok=;

         }

     }

     return ;

 }

 int dfs(int p,int s,int pre)

 {

     clo[p] = s%+;

     for (int i=;i<G[p].size();i++)

     {

         int v = G[p][i];

         if (v==pre) continue;

         if (!clo[v])

         {

             if (!dfs(v,s+,p))

                 return ;

         }

         else if(clo[v]==clo[p]) return ;

     }

     return ;

 }

 int bipartite()

 {

     memset(clo,,sizeof(clo));

     if (!dfs(,,-)) return ;

     return ;

 }

 int main()

 {

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         for (int i=;i<=n;i++) G[i].clear();

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

         {

             int x,y;

             scanf("%d%d",&x,&y);

             G[x].push_back(y);

             G[y].push_back(x);

         }

         if (!check())

             printf("0\n");

         else if (!bipartite())

             printf("%lld\n",(LL)n*(n-)/-m);

         else

         {

             LL b=,w=;

             for (int i=;i<=n;i++)

             {

                 if (clo[i]==) b++;

                 else w++;

             }

             printf("%lld\n",b*w-m);

         }

     }

     return ;

 }

巴特西

3 Steps(二分图)

C - 3 Steps

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

最新文章

热门文章