2020-2021:teams:acm_life_from_zero:5.02-5.08
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:5.02-5.08 [2020/05/08 22:28] holmium |
2020-2021:teams:acm_life_from_zero:5.02-5.08 [2020/05/15 22:41] (当前版本) holmium [姜维翰] |
||
|---|---|---|---|
| 行 278: | 行 278: | ||
| cout<<endl; | cout<<endl; | ||
| - | <code> | + | </code> |
| - | ====== 本周推荐 ====== | + | |
| - | ===== 李元恺 ===== | + | |
| + | ====== 袁熙 ====== | ||
| + | ===== 专题 ===== | ||
| + | 没有专题 | ||
| + | ===== 比赛 ===== | ||
| + | 没有比赛 | ||
| + | ===== 题目 ===== | ||
| + | CF1344C Quantifier Question DFS | ||
| + | |||
| + | 理解一下题意：给E,V~2e5的图，若无环，求有多少点，满足是其所在连通块上点编号最小的点 | ||
| + | |||
| + | 花的时间有点久，写之前想的不太充分，只考虑了后面的点 | ||
| + | 实际解法：做正向和逆向的拓扑排序，确定点是否为编号最小 | ||
| + | |||
| + | <code cpp> | ||
| + | #include <bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define tmp(x) std::cout<<"& "<<(x)<<" &\n" | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);--i) | ||
| + | using namespace std; | ||
| + | |||
| + | const int maxn=2e5+100; | ||
| + | const int mo=998244353; | ||
| + | |||
| + | int ck[maxn],deg[maxn],vis[maxn],vs[maxn],vss[maxn],rdeg[maxn]; | ||
| + | vector<int> g1[maxn],g2[maxn]; | ||
| + | int n,m,u,v,pt; | ||
| + | inline int read(){ | ||
| + | int x=0,f=1; | ||
| + | char c=getchar(); | ||
| + | while(c>'9'||c<'0'){ | ||
| + | if(c=='-')f=-1; | ||
| + | c=getchar(); | ||
| + | } | ||
| + | while(c>='0'&&c<='9'){ | ||
| + | x=x*10+c-'0';c=getchar(); | ||
| + | } | ||
| + | return x*f; | ||
| + | } | ||
| + | |||
| + | |||
| + | queue<int> qq; | ||
| + | queue<int> q; | ||
| + | void topo(){ | ||
| + | for(int i=1;i<=n;++i){ | ||
| + | vs[i]=vss[i]=i; | ||
| + | if(!deg[i])vis[i]=1,q.push(i); | ||
| + | if(!rdeg[i])qq.push(i); | ||
| + | } | ||
| + | while(!q.empty()){ | ||
| + | int x=q.front();q.pop(); | ||
| + | for(int i=0;i<g1[x].size();++i){ | ||
| + | vs[g1[x][i]]=min(vs[x],vs[g1[x][i]]); | ||
| + | if(--deg[g1[x][i]]==0)vis[g1[x][i]]=1,q.push(g1[x][i]); | ||
| + | } | ||
| + | } | ||
| + | while(!qq.empty()){ | ||
| + | int x=qq.front();qq.pop(); | ||
| + | for(int i=0;i<g2[x].size();++i){ | ||
| + | vss[g2[x][i]]=min(vss[x],vss[g2[x][i]]); | ||
| + | if(--rdeg[g2[x][i]]==0)qq.push(g2[x][i]); | ||
| + | } | ||
| + | } | ||
| + | rep(i,1,n)if(!vis[i]){ | ||
| + | printf("-1\n");return; | ||
| + | } | ||
| + | rep(i,1,n)if(vs[i]==i&&vss[i]==vs[i])++pt,ck[i]=1; | ||
| + | |||
| + | printf("%d\n",pt); | ||
| + | rep(i,1,n){ | ||
| + | if(ck[i])printf("A"); | ||
| + | else printf("E"); | ||
| + | } | ||
| + | printf("\n"); | ||
| + | } | ||
| + | int main() { | ||
| + | freopen("in.txt","r",stdin); | ||
| + | n=read(),m=read(); | ||
| + | rep(i,1,m){ | ||
| + | u=read(),v=read(); | ||
| + | g1[u].push_back(v),g2[v].push_back(u); | ||
| + | ++deg[v],++rdeg[u]; | ||
| + | } | ||
| + | topo(); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | ====== 本周推荐 ====== | ||
| + | ===== 李元恺 ===== | ||
| + | 推荐后缀数组 | ||
| + | ===== 袁熙 ===== | ||
| + | CF1344F 高斯消元 | ||
| + | [[http://codeforces.com/contest/1344/problem/F|题目链接]]（线性代数题？） | ||
| + | ===== 姜维翰 ===== | ||
| + | 关于给定各顶点度数时如何判定能否构成图，可以参考这个链接[[https://en.wikipedia.org/wiki/Graph_realization_problem]] | ||
2020-2021/teams/acm_life_from_zero/5.02-5.08.1588948081.txt.gz · 最后更改: 2020/05/08 22:28 由 holmium
