CSES - Building Roads | Xây đường
Xem PDF
Điểm:
1100 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Byteland có \(n\) thành phố, và \(m\) con đường đường giữa chúng. Mục tiêu là xây dựng các con đường mới để có một tuyến đường giữa hai thành phố bất kỳ.
Nhiệm vụ của bạn là tìm ra số lượng đường tối thiểu cần thiết, đồng thời xác định những con đường nào nên được xây dựng.
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và con đường đường. Các thành phố được đánh số \(1,2,\ldots,n\).
- Sau đó, có \(m\) dòng mô tả các con đường. Mỗi dòng có hai số nguyên \(a\) và \(b\): có một đường giữa các thành phố đó.
- Một con đường luôn kết nối hai thành phố khác nhau, và có nhiều nhất một con đường giữa hai thành phố bất kỳ.
Output
- Đầu tiên in một số nguyên \(k\): số lượng con đường cần thiết.
- Sau đó, in \(k\) dòng mô tả các con đường mới. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
Constraints
- \(1 \le n \leq 10^5\)
- \(1 \leq m \leq 2 \cdot 10^5\)
- \(1 \leq a, b \leq n\)
Example
Sample input
4 2
1 2
3 4
Sample output
1
2 3
Bình luận
var a,b,c,i,n,m:longint; u,v,u1,v1,d:array[1..400001] of longint; vi:array[1..200000] of boolean; procedure dfs(so:longint); var fex:longint; begin for fex:=d[so-1]+1 to d[so] do if vi[v[fex]] then begin vi[v[fex]]:=false; dfs(v[fex]); end; end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l;j:=r; x:=u[(l+r) div 2]; repeat while u[i]<x do inc(i); while x\<u[j] do dec(j); if not(i>j) then begin y:=u[i];u[i]:=u[j]; u[j]:=y;y:=v[i];v[i]:=v[j]; v[j]:=y;inc(i);j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r) end; begin read(m,n); for i:=1 to n do begin read(u[i],v[i]); u[i+n]:=v[i]; v[i+n]:=u[i]; inc(d[v[i]]); inc(d[u[i]]); end; sort(1,2*n); for i:=1 to m do d[i]:=d[i-1]+d[i]; fillchar(vi,sizeof(vi),true); for i:=1 to m do if vi[i] then begin vi[i]:=false; inc(c); if c<>1 then begin u1[c-1]:=i-1; v1[c-1]:=i; end; dfs(i); end; writeln(c-1); for i:=1 to c-1 do writeln(u1[i],' ',v1[i]); end.
2 bình luận nữa