hdu2767 等价性证明(求强连通分量缩点后的出度和入度为0的个数)

2017-04-25 95点热度 0人点赞


题意:给定一些已经存在的等价性证明,要求全部等价,需要在多最少几次证明

思路:先求出强连通分量,然后进行缩点,在缩点后的图上统计入度和出度为0结点的最大值,就是需要加的边数,注意如果整个图已经是强连通,就直接是答案

Sample Input

2
4 0
3 2
1 2
1 3
 


Sample Output

4

2

//tarjan算法求强连通分量,然后求出缩点后入度和出度为0的强连通分量的个数 
#include
#include
#include
using namespace std;
const int maxn=20000+10,maxm=50000+10;
int head[maxn];
struct node{
	int to,next;
}edge[maxm];
int n,m;
int num[maxn],scc;
//num为强连通中点的个数,sc为强连通分量的个数
int dfn[maxn],low[maxn],index;
int stack[maxn],top; 
int belong[maxn];//记录点在哪个强连通分量中 
void tarjan(int u){
	int v;
	dfn[u]=low[u]=++index;
	stack[top++]=u;
	for(int i=head[u];i!=-1;i=edge[i].next){
		v=edge[i].to;
		if(!dfn[v]){
			tarjan(v);
			if(low[u]>low[v]) low[u]=low[v];
		}
		else if(!belong[v]&&low[u]>dfn[v])
		low[u]=dfn[v];
	}
	if(dfn[u]==low[u]){
		scc++;
		do{
			v=stack[--top];
			belong[v]=scc;
			num[scc]++;
		}while(u!=v);
	}
}
int main(){
	int u,v;
	int T;
	cin>>T;
	while(T--){
		scanf("%d%d",&n,&m);
		//init
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(num,0,sizeof(num));
		memset(belong,0,sizeof(belong));
		scc=index=top=0;
		memset(head,-1,sizeof(head));
		for(int i=0;i

hdu2767 等价性证明(求强连通分量缩点后的出度和入度为0的个数)

一个强连通分量的low不一定全都相等,如上图。

未经允许不得转载!hdu2767 等价性证明(求强连通分量缩点后的出度和入度为0的个数)

本文地址:https://ai.52learn.online/601

站长邮箱:ai52learn@foxmail.com