QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91283#2341. Dead-End DetectorpuiRE 0ms0kbC++141.6kb2023-03-28 10:55:222023-03-28 10:55:25

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:55:25]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-03-28 10:55:22]
  • 提交

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