题目链接:   hdu
2767

题目大意:   给定有向图，问至少加入多少条边可以使得其成为强联通图

解题思路:   Kosaraju找联通分量，并缩成点

                  缩点之后形成一个或者多个DAG，题意不保证图联通

                  统计缩点后Max(入度为0顶点数，出度为0顶点数)

                  对于缩点后的图分两种情况：

                  第一种情况是图中的顶点可以到达：

                  这个时候只需要将每个入度或出度为0顶点都建立环，也就是添加三条边

                  第二种情况某些点不能到达：

                  则将这些点连成一个环，也需要顶点数目条边

代码:

[cpp] view
plaincopy

1. //Final   Kosaraju+缩点  至少添加Max(入度为0的顶点数，出度为0的顶点数)的边可成联通图  
2. #pragma comment(linker, "/STACK:10240000000,10240000000")  
3. #include <stdio.h>  
4. #include <string.h>  
5. #include <stdlib.h>  
6. #define MAX 20010  
7. struct snode{  
8.     int to,next;  
9. }edge1[MAX*20],edge2[MAX*20];  
10. int n,k,Index1,Index2,pre1[MAX],pre2[MAX],list[MAX],visit[MAX];  
11. int In[MAX],To[MAX],father[MAX];  
12. void Add_edge(int a,int b)  //建立正向逆向图  
13. {  
14.     if(a==b)  
15.         return ;  
16.     edge1[Index1].to=b,edge1[Index1].next=pre1[a];  
17.     pre1[a]=Index1++;  
18.     edge2[Index2].to=a,edge2[Index2].next=pre2[b];  
19.     pre2[b]=Index2++;  
20. }  
21.   
22. void Add_edge2(int a,int b) //建立缩点之后的图  
23. {  
24.     if(a==b)  
25.         return ;  
26.     edge2[Index2].to=b,edge2[Index2].next=pre2[a];  
27.     pre2[a]=Index2++;  
28.     In[b]++; To[a]++;  
29. }  
30.   
31. void Kosaraju(int u)         //Kosaraju搜索联通分量  
32. {  
33.     visit[u]=1;  
34.     for(int i=pre1[u];i!=-1;i=edge1[i].next)  
35.     {  
36.         if(!visit[edge1[i].to])  
37.         {  
38.             Kosaraju(edge1[i].to);  
39.         }  
40.     }  
41.     list[k++]=u;    //***  
42. }  
43.   
44. void DFS(int u,int Father)   //逆向图搜索  
45. {  
46.     int i;  
47.     visit[u]=2;  
48.     father[u]=Father;  
49.     for(i=pre2[u];i!=-1;i=edge2[i].next)  
50.     {  
51.         if(visit[edge2[i].to]==1)  
52.         {  
53.             DFS(edge2[i].to,Father);  
54.         }  
55.     }  
56. }  
57.   
58. int main()  
59. {  
60.     int i,j,m,a,b,c,t,k1,k2;  
61.     scanf("%d",&t);  
62.     while(t--)  
63.     {  
64.         Index1=Index2=0;  
65.         memset(To,0,sizeof(To));  
66.         memset(In,0,sizeof(In));  
67.         memset(pre1,-1,sizeof(pre1));  
68.         memset(pre2,-1,sizeof(pre2));  
69.         memset(visit,0,sizeof(visit));  
70.         memset(father,0,sizeof(father));  
71.         scanf("%d%d",&n,&m);  
72.         for(i=0;i<m;i++)  
73.         {  
74.             scanf("%d%d",&a,&b);  
75.             Add_edge(a,b);  
76.         }  
77.         for(i=1,k=0;i<=n;i++)    
78.         {  
79.             if(!visit[i])     //如果那个点从来没有访问过正向访问  
80.             {  
81.                   
82.                 Kosaraju(i);  
83.   
84.             }  
85.         }     
86.         for(j=k-1,c=0;j>=0;j--)  
87.         {  
88.             if(visit[list[j]]==1)  //全部访问过一遍则逆向访问  
89.             {  
90.                 DFS(list[j],++c);  
91.             }  
92.         }   
93.         if(c==1)             //如果缩成一个点则已经是联通通图了  
94.         {  
95.             printf("0\n");  
96.             continue;  
97.         }  
98.         Index2=0;  
99.         memset(pre2,-1,sizeof(pre2));  
100.         for(i=1;i<=n;i++)  
101.         {  
102.             for(j=pre1[i];j!=-1;j=edge1[j].next)  
103.             {  
104.                 int v=edge1[j].to;  
105.                 Add_edge2(father[i],father[v]);  
106.             }  
107.         }  
108.         for(i=1,k1=k2=0;i<=c;i++)  
109.         {  
110.             if(In[i]==0)   //***Max(入度为0的顶点数,出度为0的顶点数);  
111.                 k1++;  
112.             if(To[i]==0)   //  
113.                 k2++;  
114.         }  
115.         if(k1>k2)  
116.             printf("%d\n",k1);  
117.         else  
118.             printf("%d\n",k2);  
119.     }  
120.     return 0;  
121. }