图论模板
程序员文章站
2022-05-22 14:35:56
...
欧拉图
在无向图中，每个点的度数都是偶数，则存在欧拉回路。
在有向图中，每个点的入度等于出度，则存在欧拉回路。
void dfs(int u){
if(vis[u]) return;
vis[u]=true;
cnt+=(int)g[u].size()&1;//度数
for(int v=0;v<g[u].size();v++){
if(g[u][v]){
dfs(g[u][v]);
}
}
return;
}
int solve(){
int ans=0;//求非连通量
memset(vis,false,sizeof(vis));
for(int i=1;i<=m;i++){
if(!vis[i]&&du[i]){
cnt=0,dfs(i);
ans+=max(cnt,2);
}
}
return ans/2;
}