欧拉回路找环蒟蒻求助
查看原帖
欧拉回路找环蒟蒻求助
226485
柳苏明楼主2020/11/13 20:27

rt,WA50pts实在不知道哪有问题了,求大佬帮助

#include <cstdio>
#include <cctype>
#include <vector>

namespace Quick {
	class InStream {
	private:
		char buf[1<<21],*p1,*p2,failed;
		inline char getc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
		template<class Type> inline int read(Type &x) {bool k=false;char c=getc();for(;!isdigit(c);c=getc()) {k|=(c=='-');if(c==EOF) return 0;}x=0;for(;isdigit(c);c=getc()) x=(x<<1)+(x<<3)+(c^48);x*=(k?-1:1); return 1;}
		inline int read(char *s) {*s=getc();for(;isspace(*s)||*s==EOF;*s=getc()) if(*s==EOF) return 0;for(;!isspace(*s)&&*s!=EOF;*s=getc()) s++;*s='\0'; return 1;}
	public:
		operator int() const {return ~failed;}
		InStream() {p1=p2=buf;failed=0x00;}
		~InStream() {}
		template<class Type> InStream& operator >> (Type &&x) {if(read(x)) failed=0x00;else failed=0xff;return *this;}
	}cin;
	class OutStream {
	private:
		char buf[1<<21];int p1;const int p2=1<<21;
		inline void flush() {fwrite(buf,1,p1,stdout);p1=0;}
		inline void putc(const char &c) {if(p1==p2) flush();buf[p1++]=c;}
		template<class Type> inline void write(Type x) {static char buf[25];int p=-1;if(x<0) {x*=-1;putc('-');}if(x==0) putc('0');else for(;x;x/=10) buf[++p]=x%10+48;while(~p) putc(buf[p--]);}
		inline void write(char *s) {for(;*s;s++) putc(*s);}
		inline void write(const char *s) {for(;*s;s++) putc(*s);}
		inline void write(const char &c) {putc(c);}
	public:
		OutStream() {p1=0;}
		~OutStream() {flush();}
		template<class Type> OutStream& operator << (const Type &x) {write(x);return *this;}
	}cout;
	const char endl('\n');
	template<class Type> inline Type max(const Type &a,const Type &b) {if(a<b) return b;return a;}
	template<class Type> inline Type min(const Type &a,const Type &b) {if(a<b) return a;return b;}
	template<class Type> inline void swap(Type &a,Type &b) {static Type tmp;tmp=a;a=b;b=tmp;}
	template<class Type> inline Type abs(const Type &a) {return a>=0?a:-a;}
}
using namespace Quick;

const int maxn(1e5+10),maxm(1e6+10);
int n,m;

struct Edge {
	int v,next;
	Edge(const int &v,const int &next) :v(v),next(next) {}
	Edge() {}
}e[maxm<<1];
int head[maxn],cnt=1;
inline void AddEdge(const int &u,const int &v) {
	e[++cnt]=Edge(v,head[u]);
	head[u]=cnt;
}
int degree[maxn];

std::vector<int> v[maxn];
int num;
char vis_edge[maxm<<1],vis_point[maxn];

int Dfs(const int &u) {
	if(!~vis_point[u]) {num++;return u;}
	vis_point[u]=0xff;
	int p(-1);
	for(int i(head[u]);i;i=e[i].next) {
		const int &v(e[i].v);
		if(!~vis_edge[i]) continue;
		vis_edge[i]=vis_edge[i^1]=0xff;
		if(~(p=Dfs(v))) {
			::v[num].push_back(u);
			degree[u]-=2;
		}
		if(p==u) p=-1;
		else {
			if(~p) break;
			vis_edge[i]=vis_edge[i^1]=0x00;
		}
	}
	vis_point[u]=0x00;
	return p;
}

int main(void) {
	cin>>n>>m;
	for(int i(1);i<=m;i++) {
		int u,v,x,y;cin>>u>>v>>x>>y;
		if(x^y) {
			AddEdge(u,v),AddEdge(v,u);
			degree[u]++;degree[v]++;
		}
	}
	for(int i(1);i<=n;i++) if(degree[i]&1) return cout<<"NIE"<<endl,0;
	for(int i(1);i<=n;i++)
		while(degree[i])
			Dfs(i);
	cout<<num<<endl;
	for(int i(1);i<=num;i++) {
		for(const int &j: v[i])
			cout<<j<<' ';
		cout<<endl;
	}
	return 0;
}

2020/11/13 20:27
加载中...