列表

详情

NC54385. Connections

描述

Hard times are coming to Byteland. Quantum computing is becoming mainstream and Qubitland is going to occupy Byteland. The main problem is that Byteland does not have enough money for this war, so the King of Byteland Byteman 0x0B had decided to reform its road system to reduce expenses.
Byteland has n cities that are connected by m one-way roads and it is possible to get from any city to any other city using these roads. No two roads intersect outside of the cities and no other roads exist. By the way, roads are one-way because every road has a halfway barrier that may be passed in one direction only. These barriers are intended to force enemies to waste their time if they choose the wrong way.
The idea of the upcoming road reform is to abandon some roads so that exactly 2n roads remain. Advisers of the King think that it should be enough to keep the ability to get from any city to any other city. (Maybe even less is enough? They do not know for sure.) The problem is how to choose roads to abandon. Everyone in Byteland knows that you are the only one who can solve this problem.

输入描述

Input consists of several test cases. The first line of the input contains the number of tests cases.
The first line of each test case contains n and m — the number of cities and the number of roads correspondingly (n ≥ 4, m > 2n). Each of the next m lines contains two numbers xi and yi denoting a road from city xi to city yi (1 ≤ xi, yi ≤ n, xi≠yi). It is guaranteed that it is possible to get from any city to any other city using existing roads only. For each pair (x, y) of cities there is at most one road going from city x to city y and at most one road going from city y to city x. The solution is guaranteed to exist. The sum of m over all test cases in a single input does not exceed 100 000.

输出描述

For each test case output m - 2n lines. Each line describes a road that should be abandoned. Print the road in the same format as in the input: the number of the source city and the number of the destination city. The order of roads in the output does not matter, but each road from the input may appear in the output at most once and each road in the output must have been in the input. It still must be possible to get from any city to any other city using the remaining roads.

示例1

输入: 

1
4 9
1 2
1 3
2 3
2 4
3 2
3 4
4 1
4 2
4 3

输出: 

1 3

说明:

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 53ms, 内存消耗: 10900K, 提交时间: 2020-10-06 13:34:30 

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,vis[N],mark[N][2],a[N],b[N],cnt;
vector<pair<int,int> > g[N][2];
void dfs(int x,int k){
	mark[x][k]=1;
	for(auto i:g[x][k])	if(!mark[i.first][k]){
		vis[i.second]=1;	dfs(i.first,k);
	}
}
void solve(){
	cin>>n>>m;	cnt=0;
	for(int i=1;i<=n;i++)	mark[i][0]=mark[i][1]=0,g[i][0].clear(),g[i][1].clear();
	for(int i=1;i<=m;i++){
		scanf("%d %d",&a[i],&b[i]);	vis[i]=0;
		g[a[i]][0].push_back({b[i],i});
		g[b[i]][1].push_back({a[i],i});
	}
	dfs(1,1),dfs(1,0);
	for(int i=1;i<=m;i++)	if(vis[i])	cnt++;
	cnt=2*n-cnt;
	for(int i=1;i<=m;i++)	if(!vis[i]&&cnt)	cnt--,vis[i]=1;
	for(int i=1;i<=m;i++)	if(!vis[i])	printf("%d %d\n",a[i],b[i]);
}
signed main(){
	int T;	cin>>T;
	while(T--)	solve();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 50ms, 内存消耗: 11512K, 提交时间: 2020-10-07 21:29:31 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,vis[N],mark[N][2],a[N],b[N],cnt;
vector<pair<int,int> > g[N][2];
void dfs(int x,int k)
{
	mark[x][k]=1;
	for(auto i:g[x][k])
	if(!mark[i.first][k])
	{
		vis[i.second]=1;
		dfs(i.first,k);
	}
}
void solve()
{
	cin>>n>>m;
	cnt=0;
	for(int i=1;i<=n;i++)
	mark[i][0]=mark[i][1]=0,g[i][0].clear(),g[i][1].clear();
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&a[i],&b[i]);
		vis[i]=0;
		g[a[i]][0].push_back({b[i],i});
		g[b[i]][1].push_back({a[i],i});
	}
	dfs(1,1),dfs(1,0);
	for(int i=1;i<=m;i++)
	if(vis[i])
	cnt++;
	cnt=2*n-cnt;
	for(int i=1;i<=m;i++)
	if(!vis[i]&&cnt)
	cnt--,vis[i]=1;
	for(int i=1;i<=m;i++)
	if(!vis[i])
	printf("%d %d\n",a[i],b[i]);
}
signed main()
{
	int T;
	cin>>T;
	while(T--)
	solve();
	return 0;
	
}

上一题

© 2025 nowcoder.com