LeetCode 2127 - Maximum Employees to Be Invited to a Meeting 解題心得( 題目 )
解題概念:DFS、圖論
解題方法:這題也是個圖論題，但是其實沒有很容易看出來，我們把員工A喜歡B的關係視為一個A->B的邊，所以可以把題目想成:給你一個有n點n邊的有向圖，請你找出最大環?
我們先討論找最大環怎麼找，假設題目分成很多子圖(因為圖有可能不是連通的)，我們可以發現他的邊個數跟節點數其實一定會相同，透過這個性質:代表這個圖不可能出現兩個以上的環。
這樣就好辦了，我們把目前DFS的歷程加入一個Stack，並且以一個布林陣列紀錄每個點是否已在stack中，當我們DFS到重覆元素即可往回算(利用pop檢查)得到環的大小。
但是注意這題有特例，答案真的是找最大環嗎?考慮一種案例，1和2、3和4都各別互相喜歡，根據上面的想法最大環是2，但正確答案應該是把他們分別擺一起，應該是4。所以我們考慮一種情形:如果這個子圖裡有兩人互相喜歡，也就是有大小為2的環(在此稱為小環)，則這些有小環的解可以相加，並且對於小環上的兩個點做倒過來的DFS(可以把此結構視為樹)，把"找需要的人"變成"找被需要的"，如果有很多就找最大的那個樹。
最後回到問題，答案就是"小環的加總"和"最大環"取最大值。
Java參考程式碼(變數有點多，下方有說明):
//Date:2022/1/4
//Author:En Chi Tsung(欉恩祁)
class Solution {
int cnt,max,n,c,p,beg;
boolean countLoop;
int[] fav=new int[100005];
boolean[] vis=new boolean[100005];
boolean[] ins=new boolean[100005];
Stack<Integer> s=new Stack<>();
ArrayList<ArrayList<Integer>> rev=new ArrayList<>();
public int maximumInvitations(int[] favorite) {
init();
n=favorite.length;
for(int i=0;i<n;i++) {
fav[i]=favorite[i];
rev.get(fav[i]).add(i);
}
for(int i=0;i<n;i++){
if(vis[i])continue;
if(i==fav[fav[i]]) { //have found small loop
Small_Loop(i,fav[i]);
}
}
for(int i=0;i<n;i++){
if(vis[i])continue;
s.clear();
dfs(i);//to find big loop
if(c>max)max=c;
}
return Math.max(cnt,max);
}
public void Small_Loop(int x,int y) {
cnt+=(revdfs(x)+revdfs(y));
}
public int revdfs(int x){ //反邊dfs
int mx=0;
if(vis[x])return 0;
vis[x]=true;
for(int i:rev.get(x)) {
if(i==fav[fav[i]])continue;//if it is small loop itself
mx=Math.max(revdfs(i),mx);
}
return mx+1;
}
public void dfs(int x) {
if(!ins[x]&&vis[x])return;
vis[x]=true;
if(ins[x]) { //in stack
c=0;
beg=x;
countLoop=true;//start to count
return;
}
ins[x]=true;
s.push(x);
dfs(fav[x]);
p=s.pop();
if(countLoop) {
c++;
if(p==beg) {
countLoop=false;//count end
}
}
ins[x]=false;
}
public void init() {
cnt=0;//initialize
max=0;
countLoop=false;
s.clear();
rev.clear();
Arrays.fill(vis,false);
Arrays.fill(ins,false);
for(int i=0;i<100005;i++)rev.add(new ArrayList<Integer>());
}
}
變數說明:
cnt 以小環為解的答案
max 以大環為解的答案
c 算該大環大小計數器
beg 紀錄大環的起點(我們會pop一圈，用beg即可檢查是否算完一圈)
countLoop 如果他為true則計算加一(代表目前元素在環上)
fav[i] i的喜歡對象(正方向的邊)
vis[i] 是否拜訪i
ins[i] i是否重複拜訪(in stack)
rev(型別ArrayList) 記反邊
s(型別Stack) 紀錄拜訪歷程
