竞赛讨论区 > 2021年度训练联盟热身训练赛第二场 F题求助!
头像
ムラサメsama
编辑于 2021-03-17 15:07
+ 关注

2021年度训练联盟热身训练赛第二场 F题求助!

自测多组例子和已通过的代码输出都一样 但是提交case通过率一直是0 检查了很多遍格式也没有问题 求大佬指导一下
#include<bits/stdc++.h>
using namespace std;
vector<int> edge[1005];
int n, v, e,vis[1005];
int ans = 0,rollsum=0;
void bfs(int head) {
    if (vis[head])return;
    int k[1005];
    int roll = 0;
    queue<int> q;
    q.push(head);
    vis[head] = 1;
    for (auto z : edge[head])k[z] = head;   //z点因head点入列
    while (!q.empty()) {
        int ex = q.front();
        q.pop();
        for (auto z : edge[ex]) {
            if (z == k[ex])continue;   //跳过让自己入列的点 从而可以判断环
            if (vis[z]) {   //除了让自己入列的点 遍历到进过队列的点 则存在环
                roll++;
                continue;
            }
            q.push(z);
            vis[z] = 1;
            k[z] = ex;
        }
    }
    ans++;
    if (roll)rollsum++;
}
int main(){
    //freopen("zz.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        printf("Night sky #%d: ", i);
        ans = rollsum= 0;
        memset(vis, 0, sizeof vis);
        bool apper[1005];
        memset(apper, false, sizeof apper);
        cin >> v >> e;
        for (int i = 1; i <= v; i++)edge[i].clear();
        for (int j = 0; j < e; j++) {
            int f, t;
            cin >> f >> t;
            edge[f].push_back(t);
            edge[t].push_back(f);
            apper[f] = apper[t] = true;
        }
        for (int i = 1; i <= v; i++)if(apper[i]) bfs(i);
        printf("%d constellations, of which %d need to be fixed. \n\n", ans, rollsum);
    }
    return 0;
}


全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐