AtCoder ABC 229E - Graph Destruction 解題心得( 題目 )
解題概念:併查集(Disjoint set)
解題方法:首先可以先把問題轉換成依序從n、n-1...加點和邊上去，加一個點會使答案多1，而加上邊的方式可用併查集，如果兩個點的爸爸不同代表他們處不同集合，我們就把他合併，並且將答案少1，另外這裡使用了路徑壓縮的技巧優化。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
//Author:En Chi Tsung(欉恩祁)
//Date:2021/12/12
import java.util.*;
import java.io.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,r;
public static int top,ans=0;
public static int[] dsu=new int[200005];
public static void main(String[] args) throws Exception{
int ra,rb,id=-1;
final int n=orz();
final int m=orz();
pair[] edge=new pair[m];
Stack<Integer> answ=new Stack<>();
for(int i=0;i<m;i++) {
ra=orz();
rb=orz();
if(ra>rb) {
edge[i]=new pair(rb,ra);
}
else {
edge[i]=new pair(ra,rb);
}
}
Arrays.sort(edge,new Comparator<pair>() {
public int compare(pair f,pair s) {
if(f.x>s.x)return -1;
if(f.x<s.x)return 1;
return 0;
}
});
answ.push(0);
for(int i=n;i>1;i--) {
ans++;
while(id!=m-1&&edge[id+1].x>=i) {
union(edge[id+1].x,edge[id+1].y);
id++;
}
answ.push(ans);
}
while(!answ.isEmpty()) {
bw.write(answ.pop()+"\n");
}
bw.flush();
}
public static void union(int x,int y) {
query(x);
int xset=top;
query(y);
int yset=top;
if(xset==yset)return;
ans--;
dsu[yset]=xset;
}
public static void query(int x) {
if(dsu[x]==0) {
top=x;
return;
}
query(dsu[x]);
dsu[x]=top;
}
public static int orz() throws Exception{
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class pair{
int x,y;
pair(int a,int b){
x=a;
y=b;
}
}
文章標籤
全站熱搜
