【练习】图论

F. Friendly Group

图中选择一个点-1
边两端点都选择+1
边一个端点选择-1

添加链接描述

#include<iostream>
using namespace std;
#include<vector>
#include<cstring>
const int N=300010;
int n,m;
vector<int> G[N];
int temp1,temp2;
bool vis[N];int num[N];
void dfs(int u){
vis[u]=1;
temp1++;//点数
temp2+=G[u].size()-num[u];//边数for(auto v:G[u]){if(!vis[v])num[v]++;//v的邻边中已算过的边个数
}for(auto v:G[u]){
if(!vis[v])dfs(v);
}
}int main(){
int T;cin>>T;
for(int tt=1;tt<=T;tt++){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)G[i].clear();memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));while(m--){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}int ans=0;for(int i=1;i<=n;i++){if(!vis[i]){temp1=0;temp2=0;dfs(i);ans+=max(0,temp2-temp1);}}
printf("Case #%d: %d\n",tt,ans);
}}

E1. Digital Village (Easy Version)

添加链接描述