- 1git删除本地和远程文件,解决 fatal: Not a git repository (or any of the parent directories): .git 问题_git 删除指令显示 not a
- 2git 变更commit的描述信息_git修改commit的描述
- 3嵌入式软件工程师面试题
- 4pyecharts的使用和配置_pychart
- 5深入理解动态规划DP
- 6吴恩达《面向开发者的提示词工程》_吴恩达提示词工程课
- 7Strongswan5.3.5与Android5.0.2(小米)野蛮模式的L2TPoverIPsec的对接_parsed aggressive request 0 [ sa ke no id v v v v
- 8Spark中有哪些情况会导致数据倾斜？在不同的数据倾斜问题中处理方法分别是什么？_下面哪些可能是spark数据倾斜原因
- 9Git-软件项目开发中，Git命令行提交代码基本流程_软件新版本提交测试时git要先提交吗
- 10redis 和mysql 增量同步_Redis主从复制的全量和增量同步介绍
2023牛客暑期多校第三场部分题解_2023暑假牛客多校3
赞
踩
A
直接输出两个数的差即可。再判一下无解的情况。
B
其实思路还挺顺的，首先拿的牌肯定是一段增一段减一段增一段减……的序列，并且 > n >n >n 的开头和 ≤ n \leq n ≤n 的开头两种序列是对称的，我们随便考虑一种最后答案乘以二即可。
下面称 1 1 1 ~ n n n 的数为一堆， n + 1 n+1 n+1 ~ 2 n 2n 2n 为一堆。
为了避免计重，考虑在每个序列最后一张被取走的牌的那个位置统计答案，设
f
i
,
j
f_{i,j}
fi,j 表示前
i
i
i 位合法的放置方案数，并且
i
i
i 不在的那一堆里还有
j
j
j 个没用过的数。
j j j 这一维存在的意义很明确，就是要用来转移的，先考虑对答案的贡献，分为两种：
- j j j 个全部按顺序用完，并且剩下没有数了（即 i + j = 2 n i+j=2n i+j=2n），则对答案产生贡献 2 n × f i , j 2n\times f_{i,j} 2n×fi,j
- 如果不是所有数都放完了，而且还要取走了最后一张牌（即后面不能取了），那么一定是出现了不合法的取法，即同一堆数不是按递减或递增顺序取的。假设最后这堆取了 k k k 张牌，那么一定是 k − 1 k-1 k−1 张按顺序的以及 最后一张不按顺序的，贡献为 ( i + k ) × f i , j × C j k × ( k − 1 ) (i+k)\times f_{i,j}\times C_j^k\times (k-1) (i+k)×fi,j×Cjk×(k−1)，其中 k − 1 k-1 k−1 表示选出来的 k k k 张牌中还要选一个放在最后（且不能是最小/最大的那张）。
f f f 的转移类似，具体可以看代码。
说起来多其实写起来很短，而且还没啥细节：
#include <bits/stdc++.h> using namespace std; #define maxn 610 int n,mod,C[maxn][maxn],fac[maxn]; void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);} int add(int x){return x>=mod?x-mod:x;} int f[maxn][maxn]; int main() { int Te;cin>>Te;while(Te--){ cin>>n>>mod; for(int i=0;i<=2*n;i++){ C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=add(C[i-1][j]+C[i-1][j-1]); } fac[0]=1; for(int i=1;i<=2*n;i++) fac[i]=1ll*fac[i-1]*i%mod; for(int i=0;i<=2*n;i++) for(int j=0;j<=n;j++) f[i][j]=0; f[0][n]=1; int ans=0; for(int i=0;i<2*n;i++){ for(int j=1;i+j<=2*n&&j<=n;j++){ if(i+j==2*n)add(ans,1ll*f[i][j]*2*n%mod); for(int k=2;k<=j;k++) add(ans,1ll*(i+k)*f[i][j]%mod*C[j][k]%mod*(k-1)%mod*fac[2*n-i-k]%mod); } for(int j=1;i+j<=2*n&&j<=n;j++) for(int k=1;k<=j;k++) if(2*n-i-j<=n) add(f[i+k][2*n-i-j],1ll*f[i][j]*C[j][k]%mod); } ans=2ll*ans%mod; cout<<ans<<'\n'; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
D
手玩一下发现其实只有全 0 0 0 或全 1 1 1 的矩阵才是满足要求的。
考虑一个比较粗略的证明：
首先 0 ≤ r i , c j ≤ 2 n − 1 0\leq r_i,c_j\leq 2^n-1 0≤ri,cj≤2n−1
假如第一列全是 1 1 1，那么 max ( c j ) = 2 n − 1 \max(c_j) =2^n-1 max(cj)=2n−1，则 min ( r i ) = 2 n − 1 \min(r_i)=2^n-1 min(ri)=2n−1，即所有行都是全 1 1 1。
假如第一列存在一个 0 0 0 且不在第一行，那么 max ( c j ) ≥ 2 n − 1 , min ( r i ) < 2 n − 1 \max(c_j)\geq 2^{n-1},\min(r_i)<2^{n-1} max(cj)≥2n−1,min(ri)<2n−1，与条件不符，所以不可能出现。
所以第一列要是有 0 0 0，第一行必然有一个，此时 min ( r i ) < 2 n − 1 \min(r_i)<2^{n-1} min(ri)<2n−1，要使 max ( c j ) < 2 n − 1 \max(c_j)<2^{n-1} max(cj)<2n−1，则第一行不能有 1 1 1。
由此可知，第一行全是 0 0 0，所以 min ( r i ) = 0 \min(r_i)=0 min(ri)=0，故 max ( c j ) = 0 \max(c_j)=0 max(cj)=0，即每一列都全是 0 0 0。
证毕。
说着有点儿绕，总结起来就是：
- 第一列全是 1 → 1\red\to 1→ 所有行全是 1 1 1
- 第一列有 0 → 0\red\to 0→ 第一行肯定有 0 → 0\red\to 0→第一行全是 0 → 0\red\to 0→ 所有列全是 0 0 0
所以考虑能不能将整个矩阵变成全 0 / 1 0/1 0/1 的矩阵。两种思路是一样的，就将变全 0 0 0 的吧。
首先每一行每一列至多翻转一次，重复翻转没意义。于是可以枚举第一行是否翻转，操作后假如第一行还有 1 1 1，那么只能翻转他所在的这一列来消除掉这个 1 1 1。接下来为了不改变第一行已经合法的状态，所以不能再翻转列了，看下面每一行需不需要翻转即可，假如有一行既有 1 1 1 也有 1 1 1 则无解。
其实是个很贪心很暴力的简单思路，代码如下：
#include <bits/stdc++.h> using namespace std; #define maxn 2010 #define inf 999999999 int n; char s[maxn][maxn]; bool line[maxn],col[maxn]; int get(int x,int y){ int re=s[x][y]-'0'; return (re^line[x]^col[y]); } int solve(){ int re=inf; for(int line1=0;line1<=1;line1++){ memset(line,false,sizeof(line)); memset(col,false,sizeof(col)); line[1]=line1; int tot=line1; for(int i=1;i<=n;i++) if(get(1,i))col[i]=true,tot++; for(int i=2;i<=n;i++) if(get(i,1))line[i]=true,tot++; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(get(i,j))tot=inf; re=min(re,tot); } return re; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); int ans=inf; ans=min(ans,solve()); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(s[i][j]=='1')s[i][j]='0'; else s[i][j]='1'; ans=min(ans,solve()); if(ans>=2*n)puts("-1"); else printf("%d",ans); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
E
其实就是问 是否 dfs顺序如何变化整张图每个点的深度都不变。
先跑一次bfs跑出每个点的深度，将图分层，考虑不在bfs树上的几种边 ( u , v ) (u,v) (u,v)：
- 假如 d e p u + 1 = d e p v dep_u+1=dep_v depu+1=depv，那么这种边不影响答案
- 假如 d e p u + 1 ≠ d e p v dep_u+1\neq dep_v depu+1=depv，首先基于分层图的性质不可能是 d e p u + 1 < d e p v dep_u+1<dep_v depu+1<depv，那么只可能是 d e p u + 1 > d e p v dep_u+1>dep_v depu+1>depv，假如 v v v 不支配 u u u，那么一定存在一条路径会使得 v v v 能得到更大的深度。此时答案为 No。否则，这条边一定没用，因为遍历到 u u u 时一定已经遍历过 v v v 了， u u u 无法再更新 v v v。
所以其实这题难点是会不会支配树……然而我还不会，但是上网膜了个板子魔改一下之后居然过了。
代码参考性也许不是很大：
#include<bits/stdc++.h> using namespace std; #define maxn 500010 #define cn getchar template<class TY>void read(TY &x){ x=0;int f1=1;char ch=cn(); while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();} while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1; } template<class TY>void write2(TY x){ if(x>9)write2(x/10); putchar(x%10+'0'); } template<class TY>void write(TY x){ if(x<0)putchar('-'),x=-x; write2(x); } int n,m,dfn[maxn],id[maxn],tot,dep[maxn]; int ffa[maxn],fa[maxn],semi[maxn],val[maxn],du[maxn],ff[25][maxn]; queue<int>q,q1; vector<int>cg[maxn]; struct node{ vector<int>edge[maxn]; void add(int u,int v){ edge[u].push_back(v); } void clear(int n){ for(int i=1;i<=n;i++) edge[i].clear(); } }a,b,c,d; void dfs(int x,int f){ dfn[x]=++tot,id[tot]=x,ffa[x]=f,c.add(f,x); for(int i=0;i<a.edge[x].size();++i) if(!dfn[a.edge[x][i]])dfs(a.edge[x][i],x); } int find(int x){ if(x==fa[x]) return x; int tmp=fa[x];fa[x]=find(fa[x]); if(dfn[semi[val[tmp]]]<dfn[semi[val[x]]]) val[x]=val[tmp]; return fa[x]; } int LCA(int x,int y){ if(dep[x]<dep[y]) swap(x,y); int d=dep[x]-dep[y]; for(int i=20;i>=0;i--) if(d&(1<<i)) x=ff[i][x]; for(int i=20;i>=0;i--) if(ff[i][x]^ff[i][y]) x=ff[i][x],y=ff[i][y]; return x==y?x:ff[0][x]; } inline void tarjan(){ for(int i=n;i>=2;--i){ if(!id[i]) continue; int x=id[i],res=n; for(int j=0;j<b.edge[x].size();++j){ int v=b.edge[x][j]; if(!dfn[v]) continue; if(dfn[v]<dfn[x]) res=min(res,dfn[v]); else find(v),res=min(res,dfn[semi[val[v]]]); } semi[x]=id[res],fa[x]=ffa[x],c.add(semi[x],x); } for(int x=1;x<=n;x++) for(int i=0;i<c.edge[x].size();++i) du[c.edge[x][i]]++,cg[c.edge[x][i]].push_back(x); for(int x=1;x<=n;x++) if(!du[x]) q.push(x); while(!q.empty()){ int x=q.front();q.pop();q1.push(x); for(int i=0;i<c.edge[x].size();++i) if(!--du[c.edge[x][i]]) q.push(c.edge[x][i]); } while(!q1.empty()){ int x=q1.front(),f=0,len=cg[x].size();q1.pop(); if(len) f=cg[x][0]; for(int j=1;j<len;j++) f=LCA(f,cg[x][j]); ff[0][x]=f,dep[x]=dep[f]+1,d.add(f,x); for(int p=1;p<=20;p++) ff[p][x]=ff[p-1][ff[p-1][x]]; } } int u[maxn],v[maxn]; int fid[maxn],ID,con[maxn]; void dfs2(int x){ fid[x]=++ID; for(int y:d.edge[x]) dfs2(y); con[x]=ID; } int mydep[maxn],myq[maxn],st,ed; void mybfs(){ myq[st=ed=1]=n;mydep[n]=1; while(st<=ed){ int x=myq[st++]; for(int y:a.edge[x]) if(!mydep[y]){ mydep[y]=mydep[x]+1; myq[++ed]=y; } } } int main() { int T;read(T);while(T--){ read(n);read(m); for(int i=1;i<=n;i++){ fa[i]=val[i]=semi[i]=i; dfn[i]=id[i]=dep[i]=ffa[i]=du[i]=mydep[i]=0; cg[i].clear(); }tot=0; for(int i=1;i<=m;i++){ read(u[i]);read(v[i]); u[i]=n-u[i]+1;v[i]=n-v[i]+1; a.add(u[i],v[i]),b.add(v[i],u[i]); } // root: n dfs(n,0);tarjan(); ID=0;dfs2(n);mybfs(); bool ans=true; for(int i=1;i<=m;i++) if(mydep[u[i]]+1!=mydep[v[i]]){ if(fid[u[i]]>=fid[v[i]]&&fid[u[i]]<=con[v[i]]); else {ans=false;break;} } puts(ans?"Yes":"No"); a.clear(n);b.clear(n);c.clear(n);d.clear(n); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
G
当时一眼就想到了马拉车，但是没细想，开玩笑说了个是不是什么二维马拉车的神奇科技……
其实仔细考虑马拉车的话思路是很简单的，考虑每一行，枚举上下匹配对少列，然后直接跑马拉车，每次比较就是比较两段列，这个用哈希整一下就行。
代码晚点儿补……
H
n = 1 n=1 n=1 的时候特判一下， n = 2 n=2 n=2 的时候根据哥德巴赫猜想来整就行， n = 3 n=3 n=3 其实一样，先判断总和是否大于等于 2 n 2n 2n，是的话就一定可以，假设除了 1 , 2 1,2 1,2 位置全放 2 2 2，剩下的总和是偶数那么就成功了，如果不是偶数，那么就把三号位变成 3 3 3，总和就变成偶数了。
代码如下：
#include <bits/stdc++.h> using namespace std; bool prime(long long x){ for(long long i=2;i*i<=x;i++) if(x%i==0)return false; return true; } int main() { int n;long long sum=0; cin>>n; for(int i=1;i<=n;i++){ int x;cin>>x; sum+=x; } if(sum<2*n)puts("No"); else if(n==1){ if(prime(sum))puts("Yes"); else puts("No"); }else if(n==2){ if(sum&1){ if(prime(sum-2))puts("Yes"); else puts("No"); }else puts("Yes"); }else{ puts("Yes"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
I
沿着路径走的过程肯定是贪心的，能不换颜色就不换颜色，但是每次要换什么颜色呢？只需要将这个点的颜色和后面的点取交集，尽可能往后走，直到交集为空。
于是问题变成了如何快速进行一条路径的贪心，其实这个贪心并不好拆成两段贪并且合并，所以考虑在lca处枚举一个颜色，然后看看这个颜色最多能往 x , y x,y x,y 处延伸到哪儿，比如 x x , y y xx,yy xx,yy，那么现在就拆成了 x → x x x \to xx x→xx 和 y → y y y\to yy y→yy 的两段贪心。
一段子孙到祖先的贪心时很好求的，每个点向上二分一下找到最远能延伸到的点，然后倍增跳一下就求出步数了。
另外有个小优化，就是不用每次枚举之后都重新倍增跳，只需要一开始跳一次，跳到再跳一次就会跨过lca的位置就可以了，利用这个位置的深度和枚举即可求解。
时间复杂度 O ( 60 n log n ) O(60n \log n) O(60nlogn)，加上上面的优化时间复杂度其实也不变，但是由于常数可能有点儿大实在是过不去……
代码如下：
#include <bits/stdc++.h> using namespace std; #define maxn 500010 #define inf 1000000 #define ll long long #define cn getchar template<class TY>void read(TY &x){ x=0;int f1=1;char ch=cn(); while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();} while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1; } template<class TY>void write2(TY x){ if(x>9)write2(x/10); putchar(x%10+'0'); } template<class TY>void write(TY x){ if(x<0)putchar('-'),x=-x; write2(x); } int n,m; ll c[maxn]; vector<int> to[maxn]; int sum[maxn][60]; int f[maxn][19],dep[maxn]; void dfs(int x){ for(int i=0;i<60;i++) if(c[x]>>i&1)sum[x][i]++; for(int y:to[x]){ if(y==f[x][0])continue; f[y][0]=x; for(int i=0;i<60;i++) sum[y][i]=sum[x][i]; dep[y]=dep[x]+1; dfs(y); } } int fa[maxn][19]; void getfa(){ for(int i=1;i<=n;i++){ int x=i; for(int j=18;j>=0;j--){ bool tf=false; for(int k=0;k<60;k++) if((c[f[x][j]]>>k&1) && sum[i][k]-sum[f[x][j]][k]==dep[i]-dep[f[x][j]])tf=true; if(tf)x=f[x][j]; } fa[i][0]=x; } for(int j=1;j<19;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } int getlca(int x,int y){ if(dep[x]>dep[y])swap(x,y); for(int i=18;i>=0;i--) if(dep[f[y][i]]>=dep[x])y=f[y][i]; if(x==y)return x; for(int i=18;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int dis(int x,int y){ if(dep[x]>dep[y])swap(x,y); int re=0; for(int i=18;i>=0;i--) if(dep[f[y][i]]>=dep[x]) y=f[y][i],re+=(1<<i); if(x==y)return re; for(int i=18;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i],re+=(1<<i+1); return re+2; } struct par{ int x,step; }; par calc(int x,int y){ if(x==y)return (par){y,0}; int re=0; for(int i=18;i>=0;i--) if(dep[fa[y][i]]>dep[x]) y=fa[y][i],re+=(1<<i); if(dep[fa[y][0]]<=dep[x])return (par){y,re+1}; else return (par){y,inf}; } int calc_ans(int x,int y){ int lca=getlca(x,y); if(lca==x)return calc(x,y).step-1; if(lca==y)return calc(y,x).step-1; int re=inf; par xx=calc(lca,x),yy=calc(lca,y); if(xx.step==inf||yy.step==inf)return inf; for(int i=0;i<60;i++) if(c[lca]>>i&1){ int tot=xx.step+yy.step; if(sum[xx.x][i]-sum[lca][i]==dep[xx.x]-dep[lca])tot--; if(sum[yy.x][i]-sum[lca][i]==dep[yy.x]-dep[lca])tot--; re=min(re,tot); } //优化前写法 /*for(int i=0;i<60;i++)if(c[lca]>>i&1){ int xx=x,yy=y; for(int j=18;j>=0;j--){ if(dep[f[xx][j]]>=dep[lca] && sum[f[xx][j]][i]-sum[lca][i]<dep[f[xx][j]]-dep[lca]) xx=f[xx][j]; if(dep[f[yy][j]]>=dep[lca] && sum[f[yy][j]][i]-sum[lca][i]<dep[f[yy][j]]-dep[lca]) yy=f[yy][j]; } if(sum[xx][i]-sum[lca][i]<dep[xx]-dep[lca])xx=f[xx][0]; if(sum[yy][i]-sum[lca][i]<dep[yy]-dep[lca])yy=f[yy][0]; re=min(re,calc(xx,x)+calc(yy,y)); }*/ return re; } int main() { read(n);read(m); for(int i=1;i<=n;i++)read(c[i]); for(int i=1,x,y;i<n;i++){ read(x);read(y); to[x].push_back(y); to[y].push_back(x); } dep[1]=1;dfs(1); for(int j=1;j<19;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; getfa(); for(int i=1;i<=m;i++){ int x,y;read(x);read(y); int ans=calc_ans(x,y)+dis(x,y); if(ans>=inf)puts("-1"); else write(ans),puts(""); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
J
题意一开始还没看懂……就是要找几个 1 1 1 ~ n n n 的排列，使得给出的每个偏序关系都在某个排列中存在。
其实最多只需要两个，如果整一个 1 1 1 ~ n n n 再整个 n n n ~ 1 1 1 那么所有偏序关系都有了。
那么就是要判断一下能不能一个排列整完，将偏序关系连边跑一个拓扑就行，有环就是需要两个排列，否则拓扑序就是答案。
代码如下：
#include <bits/stdc++.h> using namespace std; #define maxn 1000010 struct edge{int y,next;}e[maxn]; int first[maxn],et=0; void buildroad(int x,int y){ e[++et]=(edge){y,first[x]}; first[x]=et; } int main() { int n,m;cin>>n>>m; vector<int> du(n+1); for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; buildroad(x,y); du[y]++; } vector<int> sta,ans; for(int i=1;i<=n;i++) if(!du[i])sta.push_back(i); while(sta.size()){ int x=sta.back();sta.pop_back(); ans.push_back(x); for(int i=first[x];i;i=e[i].next){ int y=e[i].y;du[y]--; if(!du[y])sta.push_back(y); } } if(ans.size()==n){ cout<<"1\n"; for(auto i:ans) cout<<i<<' '; }else{ cout<<"2\n"; for(int i=1;i<=n;i++) cout<<i<<' '; cout<<"\n"; for(int i=n;i>=1;i--) cout<<i<<' '; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
