社区讨论
CF#WA4求调玄关!!!(急,心态已崩)
CF949CData Center Maintenance参与者 2已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @m3ej8c7m
- 此快照首次捕获于
- 2024/11/12 22:13 去年
- 此快照最后确认于
- 2025/11/04 14:50 4 个月前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXX = 1e6 + 5;
struct pp{
int x, y;
}arr[MAXX];
int n, m, h, c1, c2, dfn[MAXX], low[MAXX], scc[MAXX], vis[MAXX], cnt, tot, a[MAXX], l, viss[MAXX], sz[MAXX];
vector<int> e[MAXX], ans[MAXX];
stack<int> s;
void tarjan(int x){
s.push(x);
vis[x] = 1;
dfn[x] = low[x] = ++cnt;
for(int i = 0; i < e[x].size(); i++){
int y = e[x][i];
if(!dfn[y]){
tarjan(y);
low[x] = min(low[x], low[y]);
}else if(vis[x]){
low[x] = min(low[x], dfn[y]);
}
}
// cout << x << '\n';
if(low[x] == dfn[x]){
// cout << " " << s.top() << "\n";
tot++;
while(s.top() != x){
int tmp = s.top();
s.pop();
vis[tmp] = 0;
scc[tmp] = tot;
ans[tot].push_back(tmp);
sz[tot]++;
}
sz[tot]++;
s.pop();
ans[tot].push_back(x);
vis[x] = 0;
scc[x] = tot;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> h;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= m; i++){
cin >> c1 >> c2;
if((a[c1] + 1) % h == a[c2] % h){
e[c1].push_back(c2);
arr[++l] = {c1, c2};
}else if((a[c2] + 1) % h == a[c1] % h){
e[c2].push_back(c1);
arr[++l] = {c2, c1};
}
}
for(int i = 1; i <= n; i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i = 1; i <= l; i++){
if(scc[arr[i].x] != scc[arr[i].y]){
viss[scc[arr[i].x]] = 1;
}
}
int id = 0;
sz[0] = LLONG_MAX;
for(int i = 1; i <= tot; i++){
if(viss[i] == 0 && sz[id] > sz[i]){
id = i;
}
}
cout << sz[id] << '\n';
for(int i = 0; i < ans[id].size(); i++){
cout << ans[id][i] << " ";
}
return 0;
}
回复
共 10 条回复,欢迎继续交流。
正在加载回复...