kosaraju 76pts求助
查看原帖
kosaraju 76pts求助
398152
MinimumSpanningTree最小生成树楼主2024/8/7 11:53
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4+100,M=5e4+100;
int n,m,u[N],v[N],t[N],rt[N],k,rk,b[N],bk,cnt,scc[N],tb[N],kb,sum[N],ans,val[N];
bool flag[N];
struct node
{
	int id,last;
}a[M],ra[M],ab[M];
void add(int a1,int a2)
{
	a[++k].id=a2;
	a[k].last=t[a1];
	t[a1]=k;
}
void radd(int a1,int a2)
{
	ra[++rk].id=a2;
	ra[rk].last=rt[a1];
	rt[a1]=rk;
}
void addb(int a1,int a2)
{
	ab[++kb].id=a2;
	ab[kb].last=tb[a1];
	tb[a1]=kb;
} 
void dfs1(int x)
{
	flag[x]=true;
	for(int i=t[x];i;i=a[i].last)
	{
		if(!flag[a[i].id]) dfs1(a[i].id);
	}
	b[++bk]=x;
}
void dfs2(int x,int c)
{
	scc[x]=c;
	for(int i=rt[x];i;i=ra[i].last)
	{
		if(!scc[ra[i].id]) dfs2(ra[i].id,c);
	}
}
void kosaraju()
{
	for(int i=1;i<=n;i++)
	{
		if(!flag[i]) dfs1(i);
	}
	for(int i=n;i>=1;i--)
	{
		if(!scc[b[i]]) dfs2(b[i],++cnt);
	}
}
void dfs(int x)
{
	sum[x]++;
	flag[x]=true;
	for(int i=tb[x];i;i=ab[i].last)
	{
		if(!flag[ab[i].id]) dfs(ab[i].id);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u[i],&v[i]);
		add(u[i],v[i]),radd(v[i],u[i]);
	}
	kosaraju();
	//printf("%d",cnt);
	for(int i=1;i<=n;i++) val[scc[i]]++;
	for(int i=1;i<=m;i++)
	{
		if(scc[u[i]]!=scc[v[i]]) addb(scc[u[i]],scc[v[i]]);
	}
	for(int i=1;i<=cnt;i++) 
	{
		for(int j=1;j<=cnt;j++) flag[j]=false;
		dfs(i);
	}
	for(int i=1;i<=cnt;i++)
	{
		if(sum[i]==cnt) ans+=val[i];
	}
	printf("%d",ans);
	return 0;
} 
2024/8/7 11:53
加载中...