C++11(clang++ 3.9) 解法, 执行用时: 148ms, 内存消耗: 16348K, 提交时间: 2018-12-04 20:30:52

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct edge{int f,to,v;}a[N];
struct node{int to,id;};
bool cmp(edge a,edge b){return a.v<b.v;}
int fa[N];vector<node>g[N];
int dfn[N],low[N],num;int ans[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int x,int y){x=find(x),y=find(y),fa[x]=y;}
void tarjan(int x,int fa){
	dfn[x]=low[x]=++num;
	for(auto it:g[x]){
		int u=it.to,id=it.id;
		if(id==fa) continue;
		if(!dfn[u]){
			tarjan(u,id);low[x]=min(low[x],low[u]);
			if(dfn[x]<low[u]) ans[id]=1;
		}
		else low[x]=min(low[x],dfn[u]);
	}
}
int main(){
	int n,m,q,x,y,c;scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].f,&a[i].to,&a[i].v);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int s=i;while(a[i+1].v==a[i].v) i++;
		for(int j=s;j<=i;j++){
			x=find(a[j].f),y=find(a[j].to);
			if(x==y) continue;		
			g[x].push_back({y,j});
			g[y].push_back({x,j});
		}
		for(int j=s;j<=i;j++){
			x=find(a[j].f),y=find(a[j].to);
			if(x==y||dfn[x]) continue;
			tarjan(x,0);
		}
		for(int j=s;j<=i;j++){
			x=find(a[j].f),y=find(a[j].to);
			if(x==y) continue;
			dfn[x]=dfn[y]=0;
			g[x].clear(),g[y].clear();
			unite(x,y);
		}
	}
	int num=0;for(int i=1;i<=m;i++) if(ans[i]) num++;
	printf("%d\n",num);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 154ms, 内存消耗: 12068K, 提交时间: 2020-08-05 11:53:13

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x,y,w;
}E[200005];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
vector<int>R[200005];
int ans=0,V[200005],dfn[200005],low[200005],tot=0;
int find(int a)
{
	if(V[a]==a)return a;
	return V[a]=find(V[a]);
}
void tarjan(int x,int fa)
{
    int i,j,flag=1;
    dfn[x]=low[x]=++tot;
    for(i=0;i<R[x].size();i++)
    {
        j=R[x][i];
        if(j==fa&&flag){flag=0;continue;}
        if(!dfn[j])
        {
            tarjan(j,x);
			low[x]=min(low[x],low[j]);
            if(low[j]>dfn[x])ans++;
        }
        else low[x]=min(low[x],dfn[j]);
    }
}
int main()
{
    int i,j,k,a,b,n,m;
    scanf("%d%d%d",&n,&m,&i);
    for(i=1;i<=n;i++)V[i]=i;
    for(i=0;i<m;i++)scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);
	sort(E,E+m,cmp);
	for(i=0;i<m;i=j)
	{
		for(j=i+1;j<m&&E[i].w==E[j].w;j++);
		for(k=i;k<j;k++)
		{
			a=find(E[k].x),b=find(E[k].y);
			if(a!=b)R[a].push_back(b),R[b].push_back(a);
		}
		for(k=i;k<j;k++)
		{
			a=find(E[k].x),b=find(E[k].y);
			if(a!=b&&!dfn[a])tarjan(a,0);
		}
		for(k=i;k<j;k++)
		{
			a=find(E[k].x),b=find(E[k].y);
			R[a].clear(),R[b].clear();
			dfn[a]=dfn[b]=0;
			if(a!=b)V[a]=b;
		}
	}
	printf("%d\n",ans);
    return 0;
}