首页 > 代码库 > hdu2767 Proving Equivalences --- 强连通
hdu2767 Proving Equivalences --- 强连通
给一个图,问至少加入?多少条有向边能够使图变成强连通的。
原图是有环的,缩点建图,在该DAG图上我们能够发现,要使该图变成强连通图必须连成环
而加入?最少的边连成环,就是把图上入度为0和出度为0的点连上,那么其它的点就都能够互相到达了
所以答案就是max(入度为0的点,出度为0的点)
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 #define M 20010//图中点数 using namespace std; int sta[M],top; //Tarjan 算法中的栈 bool vis[M]; //检查是否在栈中 int dfn[M]; //深度优先搜索訪问次序 int low[M]; //能追溯到的最早的次序 int ccnt; //有向图强连通分量个数 int id; //索引號 vector<int> e[M]; //邻接表表示 vector<int> part[M]; //获得强连通分量结果 int inpart[M]; //记录每一个点在第几号强连通分量里 int degree[M]; //记录每一个强连通分量的度 vector<int> edge[M];//缩点后建图 int ans,n,m,dp[M],in[M],point[M],out[M]; void tarjan(int x) { int i,j; dfn[x]=low[x]=id++; vis[x]=1; sta[++top]=x; for(i=0;i<e[x].size();i++) { j=e[x][i]; if(dfn[j]==-1) { tarjan(j); low[x]=min(low[x],low[j]); } else if(vis[j]) low[x]=min(low[x],dfn[j]); } if(dfn[x]==low[x]) { do { j=sta[top--]; vis[j]=0; part[ccnt].push_back(j); inpart[j]=ccnt; point[ccnt]++; }while(j!=x); ccnt++; } } void solve(int n) { memset(sta,-1,sizeof sta); memset(vis,0,sizeof vis); memset(dfn,-1,sizeof dfn); memset(low,-1,sizeof low); memset(point,0,sizeof point); top=ccnt=id=0; for(int i=1;i<=n;i++) if(dfn[i]==-1) tarjan(i); } int dfs(int x) { if(dp[x]) return dp[x]; dp[x]=point[x]; int i; for(i=0;i<edge[x].size();i++) { int tmp=edge[x][i]; dp[x]=max(dp[x],point[x]+dfs(tmp)); } return dp[x]; } int main() { int n,m,i,j,a,b,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i<=n;i++) { part[i].clear(); e[i].clear(); edge[i].clear(); } while(m--) { scanf("%d%d",&a,&b); e[a].push_back(b); } solve(n); memset(in,0,sizeof in); memset(out,0,sizeof out); for(i=1;i<=n;i++)//枚举原图中的边 { for(j=0;j<e[i].size();j++) { a=inpart[i]; b=inpart[e[i][j]];// if(a!=b) { in[b]++; out[a]++; edge[a].push_back(b); } } } a=b=0; for(i=0;i<ccnt;i++)// { if(in[i]==0) a++; if(out[i]==0) b++; } if(ccnt==1) printf("0\n"); else printf("%d\n",max(a,b)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。