NC15338. Journey
描述
Mr.Frog wants to travel all over the country, and as we all know the country consists of N cities and M directed roads connecting these cities. The cities are numbered from 1 to N. The roads are numbered from 1 to M, the ith road connects the city Ui to Vi which means Mr.Frog can move to city Vi from city Ui.
Mr.Frog wants to travel all cities, and he can choose a city to start his trip casually and choose a city to end his trip casually. In order to avoid the boredom in the journey, Mr.Frog decides to make a plan that can help him arrive each city exactly once and pass through each road exactly once. Now give you the information of the cities and roads. Please tell Mr.Frog whether there exists a way that can satisfy his plan.
输入描述
The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains two integers N and M, where N is the number of cities, and M is the number of roads.Then next M lines follow, the ith line contains two integers Ui and Vi, indicating there is a directed road from city Ui to city Vi.
• 1 ≤ T ≤ 105.
• 1 ≤ N ≤ 105.
• 0 ≤ M ≤ 105.
• 1 ≤ Ui,Vi ≤ N.
• the sum of N in all test cases doesn’t exceed 106.• the sum of M in all test cases doesn’t exceed 106.
输出描述
For each test case, print a line containing “Case #x:”, where x is the test case number (starting from 1).
In the next line, print the city number in the order of his journey, if there is a way that can satisfy his plan; otherwise print “NO”.
示例1
输入:
2 4 3 1 2 2 3 3 4 4 2 1 2 3 4
输出:
Case #1: 1 2 3 4 Case #2: NO
C++11(clang++ 3.9) 解法, 执行用时: 245ms, 内存消耗: 2016K, 提交时间: 2018-03-25 12:47:52
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
int T,c=0;
cin>>T;
int nxt[100005],pre[100005];
queue<int> q;
while(T--)
{
int N,M;
scanf("%d%d",&N,&M);
for(int i=0;i<=N;i++) nxt[i]=pre[i]=0;
int u,v;
bool flag=true;
for(int i=0;i<M;i++)
{
scanf("%d%d",&u,&v);
if(!nxt[u]&&!pre[v])
{
nxt[u]=v;pre[v]=u;
}
else flag=false;
}
printf("Case #%d:\n",++c);
if(!flag||M!=N-1) {printf("NO\n");continue;}
int cnt=0,S=0;
for(int i=1;i<=N;i++)
{
if(!pre[i])
{
S=i;
break;
}
}
cnt=0;
for(int i=S;i;i=nxt[i]) cnt++;
if(cnt!=N)
{
printf("NO\n");
continue;
}
printf("%d",S);
S=nxt[S];
for(int i=S;i;i=nxt[i]) printf(" %d",i);
printf("\n");
}
return 0;
}