题目描述：输入一个联通的无向图，对于每条边，判断这条边是属于这张图的任意一个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;
}
#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速度很快，但如果只要重置某几个数值，还是直接赋值更好。
