题解 | #图的增边#
图的增边
https://www.nowcoder.com/practice/6923ecd0eaa84bcdbf8377feea0a2052
#include <bits/stdc++.h>
using namespace std;
/*
* 二分图,图的所有顶点被分为两个部分,每个部分中的某些可能是相连的,但是在相同部分的顶点之间不连接;
*/
// 染色操作!
void track(int cur,int color,vector<int>& edges,vector<vector<int>>& graph){
if(edges[cur] != -1) return ;
edges[cur] = color;
color ^= 1;
for(auto nx : graph[cur]){
track(nx, color, edges,graph);
}
}
int main() {
int n,m,u,v;
cin >> n >> m;
vector<int> edges(n+1,-1);
vector<vector<int>> graph(n+1,vector<int>());
for(int i = 0; i < m; i++){
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
long long count = 0;
/*
* 通过 深度优先搜索遍历全图,对图进行标记!
*/
track(1,1,edges,graph);
for(int i = 1; i <= n; i++){
if(edges[i] == 1) count ++;
}
count *= n-count;
cout << count - m << endl;
return 0;
}
投递美团等公司10个岗位 >
字节跳动二面108人在聊
查看6道真题和解析