一个有关最小生成树的问题

题目来源：NOI导刊，NOIP模拟试题九

题目描述：输入一个联通的无向图，对于每条边，判断这条边是属于这张图的任意一个MST、至少一个MST还是不属于任何一个MST。对应输出"any","at least one","none"。

这个问题看上去有些复杂，不过，可以确定这一点：无向图中的桥一定在每个MST中。

接着，让我们从Kruskal算法的角度分析一下。Kruskal先把边按照边权递增排序，使用并查集记录每个点属于的联通分量，如果扫描到一条边的两个点不属于同一个联通分量，那么就把这条边加入MST中，并合并两个顶点所在的联通分量。

可见，对于同一个无向图，Kruskal给出的MST的结果很大程度上取决于排序的结果，如果使用稳定的排序算法对边表排序，那么Kruskal输出的结果是唯一的。如果使用随机化快排，当存在权值相等的边时，Kruskal给出的MST就不是一成不变的了。

我们就从这里下手。

新建一张空图G。在边表中找出所有边权为w的边，保存在list中，用Kruskal合并所有边权小于w的安全边。然后，依次扫描list中的所有边(i,j)，如果i和j在同一个联通分量中，那么，显然这条边一定不属于任何一MST。否则，这条边就属于某个MST，并把这条边（两端点要改成原端点所属的联通分量）加入G中。

接着，用Tarjan算法求出G中所有的桥，这些桥必然存在任意一个MST。

按照上面的方法对所有w都运行一遍，就可以获得结果了。

代码实现：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 100005
#define MAXE 100005

typedef struct node
{
   long v,ord;
   struct node *next;
}node;

typedef struct edge
{
   long u,v,w,ord;
}edge;

long N,M;
edge e[MAXE];

node *first[MAXN];
node space[MAXE * 3];
long empty;

long fa[MAXN];   //disjoint set
long dfsn[MAXN],low[MAXN];
long T;   //DFS time
int type[MAXE];

int ecmp(const void *a,const void *b)
{
   if(((edge *)a)->w > ((edge *)b)->w)    return 1;
   return -1;
}

inline void init_fa()
{
   long i;
   for(i = 1;i <= N;i ++)
       fa[i] = i;
}

long getfa(long x)
{
   if(fa[x] != x)
       fa[x] = getfa(fa[x]);
   return fa[x];
}

inline long getmin(long a,long b)
{
   if(a < b)    return a;
   return b;
}

void init()
{
   long i;
   scanf("%ld%ld",&N,&M);
   for(i = 0;i < M;i ++)
   {
       scanf("%ld%ld%ld",&e[i].u,&e[i].v,&e[i].w);
       e[i].ord = i;
   }
}

inline void addedge(long a,long b,long ord)
{
   space[empty].next = first[a];
   space[empty].v = b;
   space[empty].ord = ord;
   first[a] = space + empty;
   empty ++;
}

void tarjan(long x,long f)   //find bridges
{
   node *p;
   T ++;
   dfsn[x] = low[x] = T;
   for(p = first[x];p != NULL;p = p->next)
       if(p->ord != f)
       {
           if(dfsn[p->v] == 0)   //not visited yet
           {
               tarjan(p->v,p->ord);
               low[x] = getmin(low[x],low[p->v]);
               if(dfsn[x] < low[p->v])
                   type[p->ord] = 2;
           }
           else
               low[x] = getmin(low[x],dfsn[p->v]);
       }
}

void solve()
{
   long i,j,k,a,b;
   long addcnt = 0;
   qsort(e,M,sizeof(edge),ecmp);
   init_fa();
   for(i = 0;i < M && addcnt < N - 1;)
   {
       for(j = i;e[j].w == e[i].w;j ++);
       //e[i to j].w are the same
       for(k = i;k < j;k ++)
       {
           a = getfa(e[k].u);
           b = getfa(e[k].v);
           if(a != b)    //it's a safe edge
           {
               type[e[k].ord] = 1;   //in at least one MST
               first[a] = first[b] = NULL;   //make space for new graph
               dfsn[a] = dfsn[b] = low[a] = low[b] = 0;  //init for tarjan
           }
       }
       T = empty = 0;
       for(k = i;k < j;k ++)   //build new graph for tarjan to find bridges
       {
           if(type[e[k].ord] == 0)    continue;
           a = getfa(e[k].v);
           b = getfa(e[k].u);
           addedge(a,b,e[k].ord);
           addedge(b,a,e[k].ord);
       }
       for(k = i;k < j;k ++)
           if(dfsn[getfa(e[k].u)] == 0)  //not visited yet
               tarjan(getfa(e[k].u),-1);
       for(k = i;k < j;k ++)   //kruskal merge
       {
           a = getfa(e[k].u);
           b = getfa(e[k].v);
           if(a != b)
           {
               fa[a] = b;
               addcnt ++;
           }
       }
       i = j;
   }
}

void output()
{
   long i;
   for(i = 0;i < M;i ++)
   {
       switch(type[i])
       {
           case 1:printf("at least one\n");break;
           case 0:printf("none\n");break;
           case 2:printf("any\n");
       }
   }
}

int main()
{
   freopen("mst.in","r",stdin);
   freopen("mst.out","w",stdout);
   init();
   solve();
   output();
   fclose(stdout);
   return 0;
}

实际代码为了提高效率，重复利用了结果，并没有完全按照前面的方法设计程序。
起初本人图方便，建空图时直接memset整个first数组，导致最后三个数据超时，改成first[a] = first[b] = NULL就全部通过了。可见虽然memset速度很快，但如果只要重置某几个数值，还是直接赋值更好。