The first title of konjaku

Original question link

Er, first simplify the meaning of the question. The general meaning is to let you blow up one of the m railways, so that two of the n cities are not connected (the idea of using and searching the set is to let you cut off one edge, so that there are two connected blocks).

If you don't look at the label, you can quickly think of an idea:

First enter m paths. Each path will have two different cities. Use the idea of bucket to count the times of each city. If a city appears only once, the railway where that city is located is key road

So he excitedly typed out the code:

#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
int f[155], u[5005], v[5005];//The f array is a bucket, recording the number of occurrences of each city, the u array is the starting point, and the v array is the ending point
int main() {
	int n, m;
	SF("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		SF("%d%d", &u[i], &v[i]);
		f[u[i]]++;//Count the number of cities
		f[v[i]]++;//ditto
	}
	for(int i = 1; i <= n; i++) {
		if(f[i] == 1) {//If a city only appears once
			PF("%d %d\n", u[i], v[i]);//Output his path
		}
	}
	return 0;
} 

Give it a try?

Listen to the WA

Er, this is a yellow question. Can you water so easily?

Why WA?

Because the idea of parallel search is to let you create two connected blocks, not to isolate a city

So we need to change our mind?

Yes, it's Kruskal's minimum spanning tree (don't ask me why I don't write and check the collection, but I'm too lazy to write, isn't the template fragrant)

The problem comes again. How to skillfully change this template?

Very simply, if we set the path between the two cities to 1, it means that it has not been bombed; Set to INT_MAX, that means don't blow up

like this:

for(int i = 1; i <= m; i++) {
	int u, v;
	SF("%d%d", &u, &v);
	s[i].u = u;
	s[i].v = v;
	s[i].w = 1;//At first, the railway was not bombed
}

Then go to bomb the railway one by one

Like this:

for(int i = 1; i <= m; i++) {
	s[i].w = INT_MAX;//Blow up the i-th railway
	KAL(i);//Template
	s[i].w = 1;//Remember to go back~
}

So how should KAL be changed?

We know that as long as two cities are not in a connected block, the path between the two cities can be selected for connection. We also know that when the path between two cities is not INT_MAX, you can also choose to connect, so we can get the following template code with a little change:

void KAL(int q) {
	for(int i = 1; i <= n; i++) {//Initialize and query set
		fa[i] = i;
	}
	int sum = 0;
	for(int i = 1; i <= m; i++) {//Traverse each edge
		int fu = fun(s[i].u);
		int fv = fun(s[i].v);
		if(fu != fv && s[i].w != INT_MAX) {//The above judgment conditions
			sum++;
			fa[fu] = fv;//Merge and query set
			if(sum == n - 1) return;//If the number of connected edges is n-1, it must be and only one connected block
		}
	}
	PF("%d %d\n", s[q].u, s[q].v);//If it is not connected after traversing all edges, it indicates that there are at least two connected blocks, which are output directly
}

Happy submission again

Quite speechless

Lost in thought again

Do you want to stop looking at the topic?

Please note: when outputting, all pairs < A, b > must be sorted from small to large according to ＾ a ＾; If a is the same, it is sorted from small to large according to B.

Didn't read the questions carefully

Cough, it's not a big problem. We just need to store our answers in the array first, then write a cmp, and finally output them uniformly

ans[++r].u = s[q].u;//Save answer
ans[r].v = s[q].v;

bool comp(node a, node b) {//Happy cmp function
	return a.u == b.u ? a.v < b.v : a.u < b.u;
}

sort(ans + 1, ans + 1 + r, comp);//sort
for(int i = 1; i <= r; i++) {//Output uniformly
	PF("%d %d\n", ans[i].u, ans[i].v);
}

Happy to submit again

Again speechless

Why?

Finally, I really can't think of it. I downloaded a data and found that a must be smaller than b

So I rallied my spirits and revised it a little again:

ans[++r].u = min(s[q].u, s[q].v);//The starting point is smaller
ans[r].v = max(s[q].u, s[q].v);//The end point is larger

After submission

Finally, ha ha ha

5ms. I don't know whether it's data water or code running fast

In this way, you have a yellow question

Real problem making process

In fact, the process of doing a problem right bit by bit is very good (starting to be sensational sobbing)

OK,see you,bye!

Hey, there seems to be something missing

Oh, I see

Code moment

#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
struct node {
	int u, v, w;
}s[10005], ans[10005];
int fa[155];
int fun(int x) {
	if(fa[x] == x) return x;
	return fa[x] = fun(fa[x]);
}
int n, m, r;
bool cmp(node a, node b) {
	return a.u == b.u ? a.v < b.v : a.u < b.u;
}
void KAL(int q) {
	for(int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	int sum = 0;
	for(int i = 1; i <= m; i++) {
		int fu = fun(s[i].u);
		int fv = fun(s[i].v);
		if(fu != fv && s[i].w != INT_MAX) {
			sum++;
			fa[fu] = fv;
			if(sum == n - 1) return;
		}
	}
	ans[++r].u = min(s[q].u, s[q].v);
	ans[r].v = max(s[q].u, s[q].v);
}
bool comp(node a, node b) {
	return a.u == b.u ? a.v < b.v : a.u < b.u;
}
int main() {
	SF("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v;
		SF("%d%d", &u, &v);
		s[i].u = u;
		s[i].v = v;
		s[i].w = 1;
	}
	sort(s + 1, s + 1 + m, cmp);
	for(int i = 1; i <= m; i++) {
		s[i].w = INT_MAX;
		KAL(i);
		s[i].w = 1;
	}
	sort(ans + 1, ans + 1 + r, comp);
	for(int i = 1; i <= r; i++) {
		PF("%d %d\n", ans[i].u, ans[i].v);
	}
	return 0;
}

Refuse to copy, start with me