QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91283 | #2341. Dead-End Detector | pui | RE | 0ms | 0kb | C++14 | 1.6kb | 2023-03-28 10:55:22 | 2023-03-28 10:55:25 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int m,n,c=0;
int path[10007];
bool printed[10007];
priority_queue <pii,vector<pii>,greater<pii>> Ans;
vector <int> adj[10007];
queue <int> Q;
//Function
int find_path(int now);
int main()
{
cin >> n >> m;
for(int i=0;i<m;i++)
{
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
path[i]=adj[i].size();
Q.push(i);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
find_path(now);
}
//Print it!!!!!!!!!!!!!!
for(int i=1;i<=n;i++)
{
if(path[i]==0)
{
continue;
}
for(int j=0;j<adj[i].size();j++)
{
if(path[adj[i][j]]==0)
{
c++;
int u = min(i,adj[i][j]);
int v = max(i,adj[i][j]);
if(printed[v]!=true && printed[u]!=true)
{
Ans.push({u,v});
printed[v]=true;
}
else if(printed[u]==true)
{
Ans.push({v,u});
}
}
}
}
cout << c << endl;
while(!Ans.empty())
{
int u = Ans.top().first;
int v = Ans.top().second;
Ans.pop();
cout << u << ' ' << v << endl;
}
return 0;
}
//Function------------------------------
int find_path(int now)
{
int have_path;
for(int i=0;i<adj[now].size();i++)
{
if(path[adj[now][i]]==1)
{
path[adj[now][i]] = 0;
path[now]--;
}
if(path[adj[now][i]] > 1)
{
have_path = adj[now][i];
}
if(path[now]==1)
{
path[now] = 0;
path[have_path]--;
Q.push(have_path);
}
}
}
/*
8 8
1 2
1 3
2 3
3 4
1 5
1 6
6 7
6 8
6 5
1 2
1 3
2 3
4 5
5 6
*/
Details
Test #1:
score: 0
Runtime Error