#117. 欧拉回路

题目描述

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

这张图是无向图。（50分）
这张图是有向图。（50分）

输入格式

第一行一个整数 tt，表示子任务编号。t∈{1,2}t∈{1,2}，如果 t=1t=1 则表示处理无向图的情况，如果 t=2t=2 则表示处理有向图的情况。

第二行两个整数 n,mn,m，表示图的结点数和边数。

接下来 mm 行中，第 ii 行两个整数 vi,uivi,ui，表示第 ii 条边（从 11 开始编号）。保证 1≤vi,ui≤n1≤vi,ui≤n。

如果 t=1t=1 则表示 vivi 到 uiui 有一条无向边。
如果 t=2t=2 则表示 vivi 到 uiui 有一条有向边。

图中可能有重边也可能有自环。

输出格式

如果不可以一笔画，输出一行 “NO”。

否则，输出一行 “YES”，接下来一行输出一组方案。

如果 t=1t=1，输出 mm 个整数 p1,p2,…,pmp1,p2,…,pm。令 e=∣pi∣e=∣pi∣，那么 ee 表示经过的第 ii 条边的编号。如果 pipi 为正数表示从 veve 走到 ueue，否则表示从 ueue 走到 veve。
如果 t=2t=2，输出 mm 个整数 p1,p2,…,pmp1,p2,…,pm。其中 pipi 表示经过的第 ii 条边的编号。

样例一

input

output

YES

1 2 -3

样例二

input

output

YES

4 1 3 5 2 6

限制与约定

1≤n≤105,0≤m≤2×1051≤n≤105,0≤m≤2×105

时间限制：1s1s

空间限制：256MB

说是模板题，然而并不容易写啊～坑的数据太多。。。

要进行各种优化。。。不然会TLE。。。UOJ Extra Test 也有一组坑点，一定要注意下！

另外：本题有重边和自环。。。

代码用的是基本法（套圈）蛤蛤蛤

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<cstring>

#include<map>

using namespace std;

int t,n,m,x,y,cur;

int head[1000010],sum[1000010],adj[1000010],cnt=1;

bool vis[1000010];

struct sdt

{

	int u,v,nxt;

}e[4001000];

stack<int>s;

inline int read()

{

	int x=0;char c=getchar();

	while(c<48||c>57)c=getchar();

	while(c>47&&c<58)x*=10,x+=c-48,c=getchar();

	return x;

}

inline void add(int x,int y)

{

	e[++cnt].u=x;

	e[cnt].v=y;

	e[cnt].nxt=head[x];

	head[x]=cnt;

	adj[x]=head[x];

}

inline int gets(int x)

{

    return x%2==0 ? x/2 : -x/2 ;

}

void dfs1(int x)

{

	while(adj[x])

	{

		if(!vis[adj[x]])

		{

			vis[adj[x]]=1;

			vis[adj[x]^1]=1;

			int k=adj[x];

			dfs1(e[k].v);

			s.push(gets(k));

			cur++;

		}

		else adj[x]=e[adj[x]].nxt;

	}

}

inline bool solve1()

{

	n=read();

	m=read();

	for(int i=1;i<=m;i++)

	{

		x=read();

		y=read();

		add(x,y);

		add(y,x);

		sum[x]++;

		sum[y]++;

	}

	for(int i=1;i<=n;i++)

	{

		if(sum[i]%2)return 0;

	}

	for(int i=1;i<=n;i++)

	{

		if(sum[i])

		{

			dfs1(i);

			break;

		}

	}

	if(cur!=m)return 0; else return 1;

}

void dfs2(int x)

{

	while(adj[x])

	{

		if(!vis[adj[x]])

		{

			vis[adj[x]]=1;

			int k=adj[x];

			dfs2(e[k].v);

			s.push(k-1);

			cur++;

		}

		else adj[x]=e[adj[x]].nxt;

	}

}

inline bool solve2()

{

	n=read();

	m=read();

	for(int i=1;i<=m;i++)

	{

		x=read();

		y=read();

		add(x,y);

		sum[x]++;

		sum[y]--;

	}

	for(int i=1;i<=n;i++)

	{

		if(sum[i])return 0;

	}

	for(int i=1;i<=n;i++)

	{

		if(head[i])

		{

			dfs2(i);

			break;

		}

	}

	if(cur!=cnt-1)return 0; else return 1;

}

int main()

{

	t=read();

	if(t==1)

	{

		if(solve1()==0)

		{

			printf("NO\n");

			return 0;

		}

		else

		{

			printf("YES\n");

			while(!s.empty())

			{

				printf("%d ",s.top());

				s.pop();

			}

			printf("\n");

		}

	}

	else

	{

		if(solve2()==0)

		{

			printf("NO\n");

			return 0;

		}

		else

		{

			printf("YES\n");

			while(!s.empty())

			{

				printf("%d ",s.top());

				s.pop();

			}

			printf("\n");

		}

	}

	return 0;

}

巴特西

UOJ#117. 欧拉回路

#117. 欧拉回路

题目描述

输入格式

输出格式

样例一

input

output

样例二

input

output

限制与约定

最新文章

热门文章