CODE FESTIVAL 2017 qual B C

CODE FESTIVAL 2017 qual B C - 3 Steps

题意：给定一个n个结点m条边的无向图，若两点间走三步可以到，那么两点间可以直接连一条边，已经有边的不能连，问一共最多能连多少条边。

题解：其实我不知道二分图的实际算法，网上有人说这可以看成是否是二分图来做。

　　有人给出了个性质（没发现>_<）：相邻奇数长度的两个点一定能连边

　　　二分图就是一个图的结点分别在两个不相交的集合S，T中，且每条边都在两个集合中。（不严谨说法）如果是二分图，那么能连的边数就是|S|*|T|-m。

　　　如果不是二分图，那么每个结点与其它结点都可以连边，结果就是n*(n-1)/2-m

　　　好像dfs是什么二分图的染色，感觉就是把边分成0，1两个组（集合）。

　　　结果很大，要用longlong，而且用exit(0)直接退出程序会方便很多。

　　 18行的意思是v不是与u不相同的颜色，也就是u,v同色，想想看u,v同色且相连，说明连接u,v的边就只在一个集合中，那就不是二分图了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 const int maxn=100010;
 9 vector<int> edge[maxn*2];
10 int tot,m,n,c[maxn];
11 
12 void dfs(int u,int col)
13 {
14     c[u]=col;
15     for(int i=0;i<edge[u].size();i++){
16         int v=edge[u][i];
17         if(c[v]==-1) dfs(v,!col);
18         if(c[v]!=!col){
19             cout<<1ll*n*(n-1)/2-m<<endl;
20             exit(0);
21         }
22     }
23 }
24 
25 int main()
26 {
27     scanf("%d%d",&n,&m);
28     memset(c,-1,sizeof(c));
29     for(int i=0;i<m;i++){
30         int u,v;
31         scanf("%d%d",&u,&v);
32         edge[u].push_back(v);
33         edge[v].push_back(u);
34     }
35     dfs(1,0);
36     int b=0,w=0;
37     for(int i=1;i<=n;i++)
38         if (c[i]) b++;
39     else w++;
40     cout<<1ll*b*w-m<<endl;
41     return 0;
42 }