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的边就只在一个集合中，那就不是二分图了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 vector<int> edge[maxn*];

 int tot,m,n,c[maxn];

 void dfs(int u,int col)

 {

     c[u]=col;

     for(int i=;i<edge[u].size();i++){

         int v=edge[u][i];

         if(c[v]==-) dfs(v,!col);

         if(c[v]!=!col){

             cout<<1ll*n*(n-)/-m<<endl;

             exit();

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     memset(c,-,sizeof(c));

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

         int u,v;

         scanf("%d%d",&u,&v);

         edge[u].push_back(v);

         edge[v].push_back(u);

     }

     dfs(,);

     int b=,w=;

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

         if (c[i]) b++;

     else w++;

     cout<<1ll*b*w-m<<endl;

     return ;

 }

巴特西

CODE FESTIVAL 2017 qual B C - 3 Steps【二分图】

CODE FESTIVAL 2017 qual B C - 3 Steps

最新文章

热门文章