Journey

题意

给你一个有向图，问能否选择一个起点，使得每个点和每条边都走且只走过一次。

解法

其实就是让你判断这个图是不是一条链。

首先链的条件有一条：。

这样约束起来就是树和环的组合（可能是一棵树加一个环）。

再把入度和出度约束在之间，这样就是。

然后通过入度为零的点就是起点，把整条链扫一遍，计算通过的节点个数，判断是否有环即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m,root,v[MAXN],indegree[MAXN],outdegree[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void work(){
    if(m!=n-1){
        printf("NO\n");
        return;
    }
    for(int i=1;i<=n;i++){
        if(indegree[i]>=2||outdegree[i]>=2){
            printf("NO\n");
            return;
        }
        if(indegree[i]==0)root=i;
    }
    int s=0;
    for(int i=root;i;i=v[i])s++;
    if(s!=n){
        printf("NO\n");
        return;
    }
    for(int i=root;i;i=v[i])printf("%d ",i);
    printf("\n");
}
void init(){
    n=read();m=read();
    for(int i=1;i<=n;i++)v[i]=indegree[i]=outdegree[i]=0;
    for(int i=1,x,y;i<=m;i++){
        x=read();y=read();
        v[x]=y;
        indegree[y]++;outdegree[x]++;
    }
}
int main(){
    int t=read();
    for(int cases=1;cases<=t;cases++){
        printf("Case #%d:\n",cases);
        init();
        work();
    }
    return 0;
}