SP211 PRIMIT - Primitivus recurencis
欧拉回路
Warning: enormous Input/Output data
警告：巨大的输入/输出
经过若干（11）次提交后，我终于明白了，真的要把数组开大。
题意： 给定 t 组数据，每组数据有n条有向边（对，没给范围），每个点的编号<=1000。
打印一串最短的数列包括所有有向边。
这是满足样例的一组解：(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)
分析样例发现，编号为2,4,8的3个点是奇点（此处指出度>入度的点）。而答案为15=12+3=边数+奇点数
我们就可以联想到欧拉回路。
你需要知道一件事：对于每个满足欧拉回路性质的图，不管你怎么走，总能一次性把所有边走一遍。（自寻死路不算qwq）
而满足样例的一组解可拆分为：(8, 5, 1, 4, 2, 3, 9, 6) (4, 5, 7, 6) (2, 8, 6)
显然走了3次，起点为8,4,2。
答案就十分显然了。
不，并没有结束。因为我们忽略了图的连通性和没有奇点的图。
对于没有奇点的图，显然我们要走一次，数列长度为 边数+1。
我们可以用dfs把以上情况一起处理掉。
注意dfs只需要把点遍历一遍，而不用遍历边（会T掉），原因见上↑
（这种冷门题没人看得见吧QAQ）
code：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; template <typename T> inline T max(T &a,T &b) {return a>b ?a:b;} template <typename T> inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); } template <typename T> inline void output(T x){ if(!x) {putchar(48); return ;} int wt[50],l=0; while(x) wt[++l]=x%10,x/=10; while(l) putchar(wt[l--]+48); } int t[3002],ans,mxd,n,tt,u,v,_top,st[3000002]; int cnt,hd[3002],nxt[3000002],ed[3002],poi[3000002];//尽量开大 bool vis[3002],appear[3002]; inline void add(int x,int y){ //邻接表 nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt; ed[x]=cnt; poi[cnt]=y; ++t[x]; --t[y]; } inline void dfs(int u){ //dfs遍历点 vis[u]=1; for(int i=hd[u];i;i=nxt[i]) if(!vis[poi[i]]) dfs(poi[i]); } int main(){ scanf("%d",&tt); while(tt--){ memset(appear,0,sizeof(appear)); //该清空的都清空一遍 memset(vis,0,sizeof(vis)); memset(t,0,sizeof(t)); memset(hd,0,sizeof(hd)); memset(nxt,0,sizeof(nxt)); memset(ed,0,sizeof(ed)); memset(poi,0,sizeof(poi)); read(n); ans=n; mxd=cnt=0; //边数是固定的，可以提出来 for(int i=1;i<=n;++i){ read(u); read(v); mxd=max(mxd,max(u,v)); add(u,v); appear[u]=appear[v]=1; } for(int i=1;i<=mxd;++i) if(t[i]>0) ans+=t[i],dfs(i); //有奇点的图 for(int i=1;i<=mxd;++i) if(!vis[i]&&appear[i]) dfs(i),++ans; //没有奇点的图 output(ans); putchar(' '); }return 0; }