ennnn……zz的自己，(T1)不会判断是否满足二分单调，(T2)i和1傻傻分不清，tarjan点双缩点好不容易打对了，审题好不容易审对了，代码实现还废了……ennnn
1.匹配（题目也是明显）
这题不满足二分，答案不单调，不单调，不单调：abcdabc和abcd 4满足3不满足（请用脑子做题谢谢）
读入处理hash值（记得unsigned long long）和p（进制）的阶乘
for一遍长度处理一下
注意细节
2.回家（tarjan点双缩点）
遗憾，好不容易思路正解了，因为把i打成了1……
结论还是要把板子码熟，调了半个小时板子
缩完点后dfs找到1～n的路径上缩点个数（不包括1和n）
这题另一个WA点是判断是否有1和n，
所以从n到1dfs（从1到n也行）中回溯时 如果存父亲那最后要判断n是否除去，存儿子判断1是否除去，恩码对就行了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 6 using namespace std; 7 #define maxn 400010 8 #define maxm 800010 9 const int L=1<<20|1; 10 char buffer[L],*S,*T; 11 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) 12 inline int read() 13 { 14 register int e; register char ch; 15 while(ch=getchar(),ch<‘0‘||ch>‘9‘); e=(ch^48); 16 while(ch=getchar(),ch>=‘0‘&&ch<=‘9‘) e=(e<<1)+(e<<3)+(ch^48); 17 return e; 18 } 19 int t,n,m,u,v,root,qj,a[maxm],hh; 20 int head[maxm],js,ne[maxm*2],to[maxm*2]; 21 void qxx(int fr,int tt) 22 { 23 to[++js]=tt; 24 ne[js]=head[fr]; 25 head[fr]=js; 26 } 27 int dfn[maxn],low[maxn],tot,cut[maxn],point[maxm],num,belong[maxm],s[maxm],tail; 28 vector<int> dc[maxm]; 29 void tarjan(int ro,int fa) 30 { 31 int flag=0; 32 dfn[ro]=low[ro]=++tot; 33 s[++tail]=ro; 34 if((ro!=root)&&(!head[ro])) 35 { 36 dc[++num].clear(); 37 dc[num].push_back(ro); 38 return ; 39 } 40 for(int i=head[ro];i;i=ne[i]) 41 { 42 int son=to[i]; 43 if(son!=fa) 44 { 45 if(!dfn[son]) 46 { 47 tarjan(son,ro); 48 low[ro]=min(low[ro],low[son]); 49 if(low[son]>=dfn[ro]) 50 { 51 flag++; 52 if((ro!=root)||(flag>1)) cut[ro]=1; 53 num++; 54 dc[num].clear(); 55 int tmp; 56 while(1) 57 { 58 tmp=s[tail--]; 59 dc[num].push_back(tmp); 60 //belong[tmp]=num; 61 if(tmp==son) break; 62 } 63 dc[num].push_back(ro); 64 } 65 } 66 else low[ro]=min(low[ro],dfn[son]); 67 } 68 } 69 } 70 void dfs(int ro) 71 { 72 if(ro==belong[1]) 73 { 74 qj=1; 75 return ; 76 } 77 cut[ro]=1; 78 for(int i=head[ro];i;i=ne[i]) 79 { 80 int son=to[i]; 81 if(!cut[son]) 82 { 83 dfs(son); 84 if(qj==1) 85 { 86 if(point[ro]&&point[ro]!=n) a[++hh]=point[ro]; 87 return ; 88 } 89 } 90 } 91 } 92 int main() 93 { 94 /*freopen("sj.in","r",stdin); 95 freopen("sj.out","w",stdout);*/ 96 t=read(); 97 while(t--) 98 99 { 100 memset(a,0,sizeof(a)); memset(head,0,sizeof(head)); memset(ne,0,sizeof(ne)); 101 memset(to,0,sizeof(to)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); 102 memset(belong,0,sizeof(belong)); memset(point,0,sizeof(point)); memset(cut,0,sizeof(cut)); 103 memset(s,0,sizeof(s)); root=0; js=0; qj=0; hh=0; num=0; tot=0; tail=0; 104 n=read(); m=read(); 105 for(int i=1;i<=m;++i) 106 { 107 u=read(); v=read(); 108 if(u!=v) 109 { 110 qxx(u,v); 111 qxx(v,u); 112 } 113 } 114 root=1; 115 tarjan(1,0); 116 tot=num; 117 for(int i=1;i<=n;++i) 118 { 119 if(cut[i]) 120 { 121 belong[i]=++tot; 122 point[tot]=i; 123 } 124 } 125 js=0; 126 memset(head,0,sizeof(head)); memset(ne,0,sizeof(ne)); memset(to,0,sizeof(to)); 127 for(int i=1;i<=num;++i) 128 for(int j=0;j<dc[i].size();++j) 129 { 130 int ls=dc[i][j]; 131 if(cut[ls]) 132 { 133 qxx(belong[ls],i); 134 qxx(i,belong[ls]); 135 } 136 else belong[ls]=i; 137 } 138 num=tot; 139 memset(cut,0,sizeof(cut)); 140 dfs(belong[n]); 141 sort(a+1,a+hh+1); 142 printf("%d\n",hh); 143 for(int i=1;i<=hh;++i) printf("%d ",a[i]); 144 printf("\n"); 145 } 146 return 0; 147 }
3.
原文：https://www.cnblogs.com/qwertyuiopasdfghjklzxcvbnm/p/11246280.html
