以前写过这个题，因为还就不写tarjan了，用这道题熟悉一下。
题目大意： 给定一个n (n<=100)个点的有向图，问： Q1、最少需要选择多少个点，使得从这些点出发能遍历完整个图; Q2、最少需要添加多少条有向边，使得整个图成为连通图;分析： 开始Q1我想复杂了，先说Q2吧，和hdu2767一样，当时我自己ac了hdu2767，可是做Q2的时候又一下没想到，便找出了原来的代码…… 先由Tarjan算法求出强连通分量后进行缩点，得到每个强连通分量的入度in[]，出度out[]; Q1： 入度为0的强连通分量个数; Q2： max( 入度为0的强连通分量个数 ， 出度为0的强连通分量个数 );//题解 转自某神牛blog，忘了。。。代码自己的。
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 #define M 100100 6 #define N 5000 7 using namespace std; 8 int n,m,cnt,t,divg,belong[N],head[M],next[M],to[M],dfn[N],low[N],in[N],out[N],p,stack[N],innum,outnum; 9 bool vis[N],fg[N]; 10 inline void add(int u,int v) 11 { 12 to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; 13 } 14 void read() 15 { 16 memset(vis,0,sizeof vis); 17 memset(dfn,0,sizeof dfn); 18 memset(in,0,sizeof in); 19 memset(out,0,sizeof out); 20 memset(head,-1,sizeof head);cnt=0; 21 divg=0; p=0; t=0;//时间标志 22 scanf("%d",&n); 23 for(int i=1,a;i<=n;i++) 24 while(scanf("%d",&a),a) add(i,a); 25 } 26 void dfs(int u) 27 { 28 t++; 29 dfn[u]=low[u]=t; 30 stack[++p]=u; fg[u]=true; 31 for(int i=head[u];~i;i=next[i]) 32 { 33 if(!dfn[to[i]]) 34 { 35 dfs(to[i]); 36 low[u]=min(low[u],low[to[i]]); 37 } 38 else if(fg[to[i]]) low[u]=min(low[u],dfn[to[i]]); 39 } 40 if(dfn[u]==low[u]) 41 { 42 divg++; 43 int tmp=-1; 44 while(tmp!=u) 45 { 46 tmp=stack[p--]; 47 belong[tmp]=divg; 48 fg[tmp]=false; 49 } 50 } 51 } 52 void go() 53 { 54 for(int i=1;i<=n;i++) 55 if(!dfn[i]) dfs(i); 56 for(int i=1;i<=n;i++) 57 for(int j=head[i];~j;j=next[j]) 58 if(belong[i]!=belong[to[j]]) 59 out[belong[i]]++,in[belong[to[j]]]++; 60 innum=outnum=0; 61 for(int i=1;i<=divg;i++) 62 { 63 if(!in[i]) innum++; 64 if(!out[i]) outnum++; 65 } 66 printf("%d\n",innum); 67 if(divg==1) printf("0\n"); 68 else printf("%d\n",max(innum,outnum)); 69 } 70 int main() 71 { 72 read(); 73 go(); 74 system("pause"); 75 return 0; 76 }