AtCoder Grand Contest 027 C ABland Yard
2024-10-19 02:14:25
思路:
用了类似拓扑排序的方法来判环
代码:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e5 + ;
vector<int> g[N];
char s[N];
bool vis[N];
int d[N][];
int que[N], top = ;
int main() {
int n, m, u, v;
scanf("%d %d", &n, &m);
scanf("%s", s);
for (int i = ; i <= m; i++) {
scanf("%d %d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
for (int i = ; i <= n; i++) {
for (int v : g[i]) {
d[v][s[i-] - 'A']++;
}
}
for (int i = ; i <= n; i++) {
if(!d[i][] || !d[i][]) que[++top] = i, vis[i] = true;
}
int now = ;
while(now <= top) {
int u = que[now];
for (int v : g[u]) {
d[v][s[u-] - 'A'] --;
if(!vis[v] && !d[v][s[u-] - 'A']) que[++top] = v, vis[v] = true;
}
now++;
}
if(top < n) puts("Yes");
else puts("No");
return ;
}
最新文章
- Maven+Spring+Spring MVC+MyBatis+MySQL,搭建SSM框架环境【转】
- NC凭证接口(Java发送流和处理返回结果)
- 记录下WIN下配置LINUX虚拟机及PYTHON环境
- iOS开发debug跟release版本屏蔽NSLog方法
- ManualResetEvent &; AutoResetEvent
- android ant 多渠道批量打包
- PCB 敷铜间距规则(转)
- Oracle 11g ORA-12514:TNS:监听程序当前无法识别连接描述符中请求的服务
- hdu5344 MZL&#39;s xor(水题)
- 转:C#中的委托和事件(续)
- Redis【第一篇】安装
- Linux下卸载Oracle 11g
- Final Destination II -- 矩阵快速幂模板题
- 【python小练】0005
- BZOJ - 3170: 松鼠聚会 (切比雪夫转曼哈顿距离)
- 学习笔记50—多重假设检验与Bonferroni校正、FDR校正
- navicat外键设置
- HDU 1203 I NEED A OFFER!(01背包+简单概率知识)
- CSS框架960Grid从入门到精通一步登天
- 【转载】webstorm忽略node_modules目录