本文主要是介绍Proving Equivalences HDU - 2767，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
求再加多少边可以使整个图构成一强连通分量 tarjan缩点即可
一开始想找缩点后有多少链 再把链连起来。。发现错的离谱
找入度为零的点和出度为零的点各有多少 取最大值即可 有点贪心的意思
因为把两个强连通分量连接的最好办法就是将度为零的点相连
还有注意坑点 只有一个强连通分量时要直接输出0
#include <bits/stdc++.h>
using namespace std;struct node
{int v;int next;
};stack <int> stk;
node edge[100010];
int first[20010],dfn[20010],low[20010],belong[20010],book[20010];
int degreein[20010],degreeout[20010];
int n,m,num,cnt;void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;return;
}void dfs(int cur)
{int i,v,t;stk.push(cur);dfn[cur]=num,low[cur]=num,book[cur]=1;num++;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(!dfn[v]){dfs(v);low[cur]=min(low[cur],low[v]);}else if(book[v]){low[cur]=min(low[cur],dfn[v]);}}if(dfn[cur]==low[cur]){cnt++;while(!stk.empty()){v=stk.top();stk.pop();book[v]=0;belong[v]=cnt;if(cur==v) break;}}return;
}void tarjan()
{int i,u,v;while(!stk.empty()) stk.pop();memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(belong,0,sizeof(belong));memset(book,0,sizeof(book));num=1,cnt=0;for(u=1;u<=n;u++){if(!dfn[u]) dfs(u);}memset(degreein,0,sizeof(degreein));memset(degreeout,0,sizeof(degreeout));for(u=1;u<=n;u++){for(i=first[u];i!=-1;i=edge[i].next){v=edge[i].v;if(belong[u]!=belong[v]){degreeout[belong[u]]++;degreein[belong[v]]++;}}}return;
}int main()
{int t,i,u,v,sum1,sum2;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);memset(first,-1,sizeof(first));num=0;for(i=1;i<=m;i++){scanf("%d%d",&u,&v);addedge(u,v);}tarjan();if(cnt==1){printf("0\n");}else{sum1=0,sum2=0;for(i=1;i<=cnt;i++){if(degreein[i]==0) sum1++;if(degreeout[i]==0) sum2++;}printf("%d\n",max(sum1,sum2));}}return 0;
}
这篇关于Proving Equivalences HDU - 2767的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
