1 条题解
-
0
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=100005; int n,m,k,s,t,ans1,ans2,num[3],col[N]; vector<int> e[N]; void dfs(int u){ for (int v:e[u]) if (col[v]==0){ col[v]=3-col[u]; num[col[v]]++; dfs(v); } } int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for (int i=1;i<=m;++i){ cin>>s>>t; e[s].push_back(t); e[t].push_back(s); } for (int i=1;i<=n;++i) if (col[i]==0){ num[1]=1;num[2]=0; col[i]=1; dfs(i); ans1+=min(num[1],num[2]); ans2+=max(num[1],num[2]); } cout<<ans1<<' '<<ans2<<"\n"; }
- 1
信息
- ID
- 803
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 3
- 上传者