View Code of Problem 3847

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int n,m;
int degc[10010];
int degr[10010];

struct edge{
	int v,next;
};
edge E[10010];
int head[10010];
int ne;
int s,e;

void addedge(int a,int b)
{
	E[ne].v=b;
	E[ne].next=head[a];
	head[a]=ne++;
}

vector<int> ans;
void dfs(int x)
{
	ans.push_back(x);
	if(x==e)
		return;
	for(int i=head[x];i!=-1;i=E[i].next)
		dfs(E[i].v);
}

int main()
{
	int t;
	scanf("%d",&t);
	int kase=0;
	while(t--)
	{
		ne=0;
		memset(head,-1,sizeof(head));
		memset(degr,0,sizeof(degr));
		memset(degc,0,sizeof(degc));
		scanf("%d%d",&n,&m);
		int a,b;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			degc[a]++;
			degr[b]++;
			addedge(a,b);
		}
		printf("Case #%d:\n",++kase);
		if(n==1&&!m)
		{
			printf("%d\n",n);
			continue;
		}
		if(!m)
		{
			puts("NO");
			continue;
		}
		bool flag=true;
		s=-1,e=-1;
		for(int i=1;i<=n;i++)
		{
			if(degr[i]==1&&degc[i]==1) continue;
			else if(!degr[i]&&s==-1&&degc[i]==1) s=i;
			else if(!degc[i]&&e==-1&&degr[i]==1) e=i;
			else 
			{
				flag=false;
				break;
			}
		}
		ans.clear();
		if(!flag) puts("NO");
		else
		{
			dfs(s);
			printf("%d",ans[0]);
			for(int i=1;i<ans.size();i++)
				printf(" %d",ans[i]);
			putchar('\n');
		}
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 3847