POJ 2762 缩点+判断是否是最长链

题目链接： http://poj.org/problem?id=2762

题目大意：

　　给定一个有向图，问是否对于任意给定的两个点x，y，满足以下两个条件之一： x能到达y 或者 y能到达x;

分析：

　　我觉得这题并不是如网上和discuss写的那样，什么拓扑排序，什么dp的;

　　首先缩点是必须的;

　　缩点得到一个DAG，直接判断它是否是一条链就可以了，因为如果是链，那么这个链必定是所谓的最长链，那么任意两个点一定是单向可达的。

代码：

poj2762

 1 /*2762    Accepted    392K    344MS    C++    2299B    2012-06-09 23:15:11*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 
10 #define mpair make_pair
11 #define pii pair<int,int>
12 #define MM(a,b) memset(a,b,sizeof(a));
13 typedef long long lld;
14 typedef unsigned long long u64;
15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
17 #define maxn 1020
18 
19 int n,m;
20 vector<int>g[maxn], adj[maxn];
21 
22 int Bcnt, Index, Top;
23 int low[maxn], dfn[maxn], sta[maxn], beg[maxn];
24 bool vis[maxn];
25 void Init_tarjan(){
26     Bcnt= Index= Top= 0;
27     for(int i=1;i<=n;++i) low[i]= dfn[i]= vis[i]= 0;
28 }
29 void Tarjan(int u){
30     low[u]= dfn[u]= ++Index;
31     sta[++Top]= u;
32     vis[u]= 1;
33     for(int i=0;i<g[u].size();++i){
34         int v= g[u][i];
35         if( !dfn[v] ){
36             Tarjan(v);
37             up_min( low[u], low[v] );
38         }
39         else if( vis[v] )
40             up_min( low[u], dfn[v] );
41     }
42     if( low[u]==dfn[u] ){
43         ++Bcnt;
44         int v;
45         do{
46             v= sta[Top--];
47             vis[v]= 0;
48             beg[v]= Bcnt;
49         }while(u!=v);
50     }
51 }
52 
53 int in[maxn];
54 void dfs(int u){
55     vis[u]= 1;
56     for(int i=0;i<g[u].size();++i){
57         int v= g[u][i];
58         if( beg[u]!=beg[v] ){
59             adj[ beg[u] ].push_back( beg[v] );
60             ++in[ beg[v] ];
61         }
62         if( !vis[v] ) dfs(v);
63     }
64 }
65 
66 int main()
67 {
68     //freopen("poj2762.in","r",stdin);
69     int T, i, x, y;
70     cin>>T;
71     while(T--){
72         scanf("%d%d", &n, &m);
73         for(i=1;i<=n;++i) g[i].clear();
74         for(i=1;i<=m;++i){
75             scanf("%d%d", &x, &y);
76             g[x].push_back( y );
77         }
78         Init_tarjan();
79         for(i=1;i<=n;++i)
80             if( !dfn[i] )
81                 Tarjan( i );
82 
83         for(i=1;i<=Bcnt;++i) adj[i].clear(), in[i]= 0;
84         fill( vis+1, vis+1+n, 0 );
85         for(i=1;i<=n;++i)
86             if( !vis[i] )
87                 dfs(i);
88 
89         int tot= Bcnt-1, s;
90         for(i=1;i<=Bcnt;++i) if( !in[i] ) { s= i; break; }
91         while( adj[s].size()==1 ){
92             tot--;
93             s= adj[s][0];
94         }
95         if( tot==0 ) puts("Yes");
96         else puts("No");
97     }
98 }