题目链接: hdu 2767
题目大意: 给定有向图,问至少加入多少条边可以使得其成为强联通图
解题思路: Kosaraju找联通分量,并缩成点
缩点之后形成一个或者多个DAG,题意不保证图联通
统计缩点后Max(入度为0顶点数,出度为0顶点数)
对于缩点后的图分两种情况:
第一种情况是图中的顶点可以到达:
这个时候只需要将每个入度或出度为0顶点都建立环,也就是添加三条边
第二种情况某些点不能到达:
则将这些点连成一个环,也需要顶点数目条边
代码:
//Final Kosaraju+缩点 至少添加Max(入度为0的顶点数,出度为0的顶点数)的边可成联通图 #pragma comment(linker, "/STACK:10240000000,10240000000") #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 20010 struct snode{ int to,next; }edge1[MAX*20],edge2[MAX*20]; int n,k,Index1,Index2,pre1[MAX],pre2[MAX],list[MAX],visit[MAX]; int In[MAX],To[MAX],father[MAX]; void Add_edge(int a,int b) //建立正向逆向图 { if(a==b) return ; edge1[Index1].to=b,edge1[Index1].next=pre1[a]; pre1[a]=Index1++; edge2[Index2].to=a,edge2[Index2].next=pre2[b]; pre2[b]=Index2++; } void Add_edge2(int a,int b) //建立缩点之后的图 { if(a==b) return ; edge2[Index2].to=b,edge2[Index2].next=pre2[a]; pre2[a]=Index2++; In[b]++; To[a]++; } void Kosaraju(int u) //Kosaraju搜索联通分量 { visit[u]=1; for(int i=pre1[u];i!=-1;i=edge1[i].next) { if(!visit[edge1[i].to]) { Kosaraju(edge1[i].to); } } list[k++]=u; //*** } void DFS(int u,int Father) //逆向图搜索 { int i; visit[u]=2; father[u]=Father; for(i=pre2[u];i!=-1;i=edge2[i].next) { if(visit[edge2[i].to]==1) { DFS(edge2[i].to,Father); } } } int main() { int i,j,m,a,b,c,t,k1,k2; scanf("%d",&t); while(t--) { Index1=Index2=0; memset(To,0,sizeof(To)); memset(In,0,sizeof(In)); memset(pre1,-1,sizeof(pre1)); memset(pre2,-1,sizeof(pre2)); memset(visit,0,sizeof(visit)); memset(father,0,sizeof(father)); scanf("%d%d",&n,&m); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); Add_edge(a,b); } for(i=1,k=0;i<=n;i++) { if(!visit[i]) //如果那个点从来没有访问过正向访问 { Kosaraju(i); } } for(j=k-1,c=0;j>=0;j--) { if(visit[list[j]]==1) //全部访问过一遍则逆向访问 { DFS(list[j],++c); } } if(c==1) //如果缩成一个点则已经是联通通图了 { printf("0\n"); continue; } Index2=0; memset(pre2,-1,sizeof(pre2)); for(i=1;i<=n;i++) { for(j=pre1[i];j!=-1;j=edge1[j].next) { int v=edge1[j].to; Add_edge2(father[i],father[v]); } } for(i=1,k1=k2=0;i<=c;i++) { if(In[i]==0) //***Max(入度为0的顶点数,出度为0的顶点数); k1++; if(To[i]==0) // k2++; } if(k1>k2) printf("%d\n",k1); else printf("%d\n",k2); } return 0; }