首页 > 其他分享 >每日一题-CF1994F

每日一题-CF1994F

时间:2024-07-30 10:40:37浏览次数:18  
标签:int 每日 CF1994F st nx 一题 500005 void hd

花30分钟发现lg翻译出错了

又花30分钟学习欧拉回路怎么求

再花30分钟等待codeforces的queue

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
vector<int> res;
struct edge{
	int v,w,nx;
}e[1000005];
int cnt,hd[500005],deg[500005],sum[500005];
void add(int u,int v,int w){
	e[++cnt]=edge{v,w,hd[u]};
	hd[u]=cnt;
}
bool vis[500005];
void dfs(int u){
	vis[u]=1;
	for(int i=hd[u];i;i=e[i].nx){
		int v=e[i].v;
		if(vis[v] || e[i].w!=0)continue;
		dfs(v);
		if(deg[v]&1)deg[v]--,deg[u]--,e[i].w=e[i^1].w=-1;
	}
}
stack<int> st;
void dfs2(int u){
	st.push(u);
	for(int i=hd[u];i;i=e[i].nx){
		int v=e[i].v;if(e[i].w==-1)continue;
		hd[u]=i;
		e[i].w=e[i^1].w=-1;
		dfs2(v);
		break;
	}
}
void work(){
	st.push(1);
	while(!st.empty()){
		int u=st.top();st.pop();
		int v=0;
		for(int i=hd[u];i;i=e[i].nx){
			if(e[i].w==-1)continue;
			hd[u]=i;
			v=e[i].v;break;
		}
		if(v)dfs2(u);
		else{
			for(int i=0;i<=sum[u];i++)res.emplace_back(u);
			sum[u]=0;
		}
	}
}
void init(){
	cnt=1;
	for(int i=1;i<=n;i++)hd[i]=0,deg[i]=0,vis[i]=0,sum[i]=0;
	res.clear();
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=m;i++){
			int u,v,w;scanf("%d%d%d",&u,&v,&w);
			if(u==v){
				if(w==1)sum[u]++;
				continue;
			}
			add(u,v,w);add(v,u,w);
			deg[u]++;deg[v]++;
		}
		bool flag=0;
		for(int i=1;i<=n;i++)
			if(!vis[i]){
				dfs(i);
				if(deg[i]&1)flag=1;
			}
		if(flag){
			puts("NO");
			continue;
		}
		work();
		printf("YES\n%d\n",res.size()-1);
		for(int i:res)printf("%d ",i);puts("");
	}
	return 0;
}  

标签:int,每日,CF1994F,st,nx,一题,500005,void,hd
From: https://www.cnblogs.com/kentsbk/p/18331795

相关文章

  • 牛客每日一题系列-001
    牛客23486小A与小B方法1:BFSfromcollectionsimportdequefromtypingimportListdefbfs(pos:tuple,direction:int)->List[List[int]]:ans=[[MAX]*Mfor_inrange(N)]vis=[[False]*Mfor_inrange(N)]queue=deque();queue.append((p......
  • 每日一题- CF1991G
    考场真是困傻了,这都不会横的放左边k列,竖的放上边k行,优先放能消的位置#include<bits/stdc++.h>usingnamespacestd;intt,n,m,k,q,a[105][105];chars[1005];intx[105],y[105];intmain(){ scanf("%d",&t); while(t--){ scanf("%d%d%d%d",&n,&m,&k......
  • 【Golang 面试 - 进阶题】每日 3 题(三)
    ✍个人博客:Pandaconda-CSDN博客......
  • 【Golang 面试 - 进阶题】每日 3 题(四)
     ✍个人博客:Pandaconda-CSDN博客......
  • 2024/07/29 每日一题
    LeetCode682棒球比赛方法1:栈模拟classSolution:defcalPoints(self,operations:List[str])->int:nums=list();ans=0foropinoperations:ifop=="+":nums.append(nums[-2]+nums[-1])......
  • 2024/07/28 每日一题
    LeetCode699掉落的方块方法1:暴力classSolution:deffallingSquares(self,positions:List[List[int]])->List[int]:n=len(positions);ans=[0]*n#记录每个方块落下后的高度fori,(left0,widen0)inenumerate(positions):......
  • 【Golang 面试 - 进阶题】每日 3 题(三)
    ✍个人博客:Pandaconda-CSDN博客......
  • 每日一知识点 - Java常用关键字
    目录......
  • GitHub每日最火火火项目(7.27)
    1. 项目名称:meta-llama/llama3项目介绍:这是MetaLlama3的官方GitHub站点。目前尚不清楚该项目的具体功能和特点,但从名称推测,可能与Llama3模型相关,或许涉及到模型的开发、训练或应用等方面。项目地址:https://github.com/meta-llama/llama32. 项目名称:Asabe......
  • GitHub每日最火火火项目(7.26)
    1. 项目名称:meta-llama/llama3项目介绍:这是MetaLlama3的官方GitHub站点。目前尚不清楚该项目的具体功能和特点,但从名称推测,它可能与Llama3模型相关,或许涉及到该模型的开发、训练或应用等方面。项目地址:https://github.com/meta-llama/llama32. 项目名称:A......