QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91285 | #2341. Dead-End Detector | pui | WA | 2ms | 3444kb | C++14 | 1.0kb | 2023-03-28 10:57:41 | 2023-03-28 10:57:44 |
Judging History
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;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3444kb