社区讨论

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 条回复,欢迎继续交流。

正在加载回复...