[TIOJ 1698] Problem H 神殿裡的觸手

作法：

考慮 Kruskal 的過程，假設現在邊權 < k 的邊都加入了，形成了好幾坨連通塊，現在看看所有邊權等於 k 的邊，如果他的兩端點在同一個連通塊那他絕對不會選到。我們要找的是一定會被選到的邊，所以如果一張新的圖，先把每個所有聯通塊縮起來當成一坨點，然後對於一條邊權 = k 的邊，如果他的兩端點在不同的連通塊上，就在新的圖裡的兩坨點之間建一條邊，這樣就可以得到必須出現在MST裡的邊就會是這張圖裡的橋。如果是橋的話顯然一定要，而如果不是的話，代表把這條邊拔掉之後剩下的邊還是可以讓該連的連起來。在實作上，因為當我們把邊權 = k 的邊都跑過一次之後，就知道等一下在找橋的時候會用到那些頂點了，所以可以不用每次換一個邊權作橋的時候都把所有的要作橋的圖清乾淨。還要注意到所有的邊都要跑到，而新的圖不一定整個連通，所以還必須多紀錄新的圖中到底有哪些頂點，要確保所有的新圖裡的頂點連出的邊都要被走到。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=400000+10 ;
struct P
{
    int x,y,dis,id ;
    bool operator < (const P &rhs) const
    {
        return dis<rhs.dis ;
    }
};
 
struct Q{int x,y;};
 
vector<P> E ;
 
int fa[maxn] ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
bool ans[maxm] ;
int ver[maxm],cnt ;
int eid[maxm] ;
vector<Q> edge ;
vector<int> v[maxn] ;
bool vis[maxn],evis[maxm] ;
int lev[maxn] ;
 
int dfs(int x,int l)
{
    int low ;
    lev[x]=low=l ;
    vis[x]=1 ;
    for(auto i : v[x]) if(!evis[i])
    {
        evis[i]=1 ;
        int to= edge[i].x==x ? edge[i].y : edge[i].x ;
        if(vis[to]) low=min(low,lev[to]) ;
        else
        {
            int tmp=dfs(to,l+1) ;
            low=min(low,tmp) ;
            if(tmp > lev[x]) ans[eid[i]]=1 ;
        }
    }
    return low ;
}
 
void Kruskal()
{
    sort(E.begin(),E.end()) ;
    for(int i=0;i<E.size();)
    {
        cnt=0 ;
        edge.clear() ;
        int j ;
        for(j=i;j<E.size() && E[j].dis==E[i].dis;j++) ;
        for(int k=i;k<j;k++)
        {
            int x=getfa(E[k].x) , y=getfa(E[k].y) ;
            if(x==y) continue ;
            ver[cnt++]=x ; ver[cnt++]=y ;
            v[x].clear() ; v[y].clear() ;
            vis[x]=vis[y]=0 ;
        }
        for(int k=i;k<j;k++)
        {
            int x=getfa(E[k].x) , y=getfa(E[k].y) ;
            if(x==y) continue ;
 
            edge.push_back((Q){x,y}) ;
            int sz=edge.size() ;
            v[x].push_back(sz-1) ;
            v[y].push_back(sz-1) ;
            eid[sz-1]=E[k].id ;
            evis[sz-1]=0 ;
        }
 
        for(int k=0;k<cnt;k++) if(!vis[ver[k]])
            dfs(ver[k],0) ;
 
        for(int k=i;k<j;k++) fa[getfa(E[k].x)]=getfa(E[k].y) ;
        i=j ;
    }
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) fa[i]=i ;
    for(int i=0;i<m;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        E.push_back((P){x,y,dis,i+1}) ;
    }
    Kruskal() ;
    int num=count(ans+1,ans+m+1,true) ;
    printf("%d\n",num) ;
    if(!num) printf("0\n") ;
    else for(int i=1;i<=m;i++) if(ans[i]) printf("%d%c",i,(--num)?' ':'\n') ;
}