QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91285#2341. Dead-End DetectorpuiWA 2ms3444kbC++141.0kb2023-03-28 10:57:412023-03-28 10:57:44

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-28 10:57:44]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3444kb
  • [2023-03-28 10:57:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int main()
{
    int n,m;
    cin >> n >> m;
    vector<int>G[n+1];
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    queue<int>q;
    int degree[n+1];
    for(int i=1;i<=n;i++)
    {
        degree[i] = G[i].size();
        if(degree[i] == 1)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        degree[G[u][0]]--;
        if(degree[G[u][0]] == 1)
        {
            q.push(G[u][0]);
        }
    }
    vector<pii>ans;
    for(int i=1;i<=n;i++)
    {
        if(degree[i] > 1)
        {
            for(auto x : G[i])
            {
                if(degree[x] == 1)
                    ans.push_back({i,x});
            }
        }
    }
    cout << ans.size() << endl;
    for(auto a : ans)
    {
        cout << a.first << " " << a.second << endl;
    }
    return 0;
}

Details

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3444kb