PKU 2762 Going from u to v or from v to u? - 單連通圖判定

題目大意：

給出一個有向圖n個頂點m條邊，判斷是否能任意選擇兩個點u,v，都至少存在一條通路從u到達v或v到達u，也就是u,v之間存在單向的通路。

分析：

首先将有向圖的極大強連通分量收縮成一個點，構成新的有向無環圖G'。現在要判斷新圖G'是一個單連通圖。即每對頂點u,v存在u->v或v->u或兩者都存在。

這個條件看起來很面熟，貌似競賽圖就是滿足這樣條件的圖。競賽圖有一個性質，競賽圖必然存在一條哈密爾頓通路，即可以存在一條極長的單向鍊把所有的頂點串起來。是以此題隻需要求最長的單向鍊即可。

此題的關鍵在于收縮強連通分支，求最長鍊用簡單的DP就好。

1. #include <stdio.h>
2. #include <memory.h>
3. #define clr(a) memset(a,0,sizeof(a))
4. #define N 1005
5. #define M 15005
6. typedef struct StrNode{
7.     int j; struct StrNode* next;
8. }Node;
9. int memp; Node mem[M]; //M>=2*|E|
10. void addEdge(Node* e[],int i,int j){
11.     Node* p = &mem[memp++];
12.     p->j=j; p->next=e[i]; e[i]=p;
13. }
14. int g_DFS_First;
15. void DFS_conn(Node* e[],int i,int mark[],int f[],int* nf){
16.     int j; Node* p;
17.     if(mark[i]) return; else mark[i]=1;
18.     if(!g_DFS_First) f[i]=*nf;  //反向搜尋，擷取連通分量編号
19.     for(p=e[i];p!=NULL;p=p->next) DFS_conn(e,p->j,mark,f,nf);
20.     if(g_DFS_First) f[(*nf)++]=i;   //正向搜尋，擷取時間戳
21. }
22. int Connection (Node* e[],int n,int con[]){
23.     int i,j,k,mark[N],ncon,time[N],ntime;//time[i]表示時間戳為i的節點
24.     Node *p,*re[N]; //反向邊
25.     clr(re);        //構造反向邊鄰接表
26.     for(i=0;i<n;i++) for(p=e[i];p!=NULL;p=p->next) addEdge(re,p->j,i);
27.     g_DFS_First = 1;    //正向DFS，獲得時間戳 
28.     clr(mark); clr(time); ntime=0;
29.     for(i=0;i<n;i++) if(!mark[i]) DFS_conn(e,i,mark,time,&ntime);
30.     g_DFS_First = 0;    //反向DFS，獲得強連通分量
31.     clr(mark); clr(con); ncon=0;
32.     for(i=n-1;i>=0;i--) if(!mark[time[i]])
33.     { DFS_conn(re,time[i],mark,con,&ncon); ncon++; }
34.     return ncon;
35. }
36. int ShrinkConnection(Node *e[],int n,Node *ce[],int con[]){
37.     int i,j,k,m; Node *p,*q;
38.     m=Connection(e,n,con);
39.     for(i=0;i<m;i++) ce[i]=NULL;
40.     for(k=0;k<n;k++) for(i=con[k],p=e[k];p!=NULL;p=p->next){
41.         for(j=con[p->j],q=ce[i];q!=NULL;q=q->next) if(q->j==j) break;
42.         if(q==NULL&&i!=j) addEdge(ce,i,j);
43.     }
44.     return m;
45. }
46. int n,m,nc;
47. int con[N],f[N];
48. Node *e[N];
49. Node *ce[N];
50. #define MAX(a,b) ((a)>(b)?(a):(b))
51. int DFS_link(Node* e[],int i,int f[]){
52.     int j,k,max=1; Node *p;
53.     for(p=e[i];p!=NULL;p=p->next){
54.         if(f[p->j]) max=MAX(max,f[p->j]+1);
55.         else{
56.             k=DFS_link(e,p->j,f);
57.             max=MAX(max,k+1);
58.         }
59.     }
60.     return f[i]=max;
61. }
62. int main()
63. {
64.     int i,j,k,ans,T;
65.     scanf("%d",&T);
66.     while(T--){
67.         //init
68.         memp=0; clr(e);
69.         //input
70.         scanf("%d%d",&n,&m);
71.         for(k=0;k<m;k++){
72.             scanf("%d%d",&i,&j);
73.             addEdge(e,i-1,j-1);
74.         }
75.         //Shrink Connection
76.         nc=ShrinkConnection(e,n,ce,con);
77.         //maxlen link
78.         clr(f); ans=1;
79.         for(i=0;i<nc;i++) if(!f[i]){
80.             k=DFS_link(ce,i,f);
81.             ans=MAX(ans,k);
82.         }
83.         if(ans==nc) puts("Yes");
84.         else puts("No");
85.     }
86.     return 0;
87. }