hdu 4324 拓扑排序

题意：给出一堆人的喜爱关系，判断有没有三角恋-_-||

其实就是判断是否存在三条边的环。

一开始我是这么想的：

先拓扑排序，如果没有环那就直接No
如果有环？挑出环里的任意一个点（拓扑排序结束后不在拓扑序里面的点就在环里），然后从这个点开始dfs，看三步之后能不能回到这个点。（可以证明，只要考察一个点就行）

然而TLE了= =

其实仔细想想可以发现，后面那个dfs没有必要。

注意一个细节：A[i][j]<>A[j][i]。也就是说若i到j不通，那么j到i一定通

可以证明，若这样的图中存在环，那么一定存在三角环（证明Reference：http://blog.csdn.net/xiaofengcanyuexj/article/details/29179639）

数据不大，邻接矩阵就ok

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 #define MAXN 2100
 6 
 7 int a[MAXN][MAXN];
 8 int d[MAXN];
 9 bool ok;
10 int N,T,x,y;
11 
12 void topsort()
13 {
14     bool circle=false;
15     int i=0;
16     while(i<N)
17     {
18         int j=1;
19         while(d[j]!=0)  j++;
20         if(j==N+1)
21         {
22             circle=true;
23             break;
24         }
25         d[j]=-1;
26         for(int k=1;k<=N;k++)
27             if(a[j][k]==1)
28             {
29                 d[k]--;
30                 a[j][k]=0;
31             }
32         i++;
33     }
34     if((circle)&&(N>=3))
35         cout<<"Yes"<<endl;
36     else
37         cout<<"No"<<endl;
38 }
39 
40 int main()
41 {
42     cin>>T;
43     for(int Times=1;Times<=T;Times++)
44     {
45         cin>>N;
46         memset(d,0,sizeof(d));
47         memset(a,0,sizeof(a));
48         char ch[2010];
49         for(int i=1; i<=N; i++)
50         {
51             scanf("%s",ch);
52             for(int j=1;j<=N;j++)
53             {
54                 if (ch[j-1]=='1')
55                 {
56                     d[j]++;
57                     a[i][j]=1;
58                 }
59             }
60         }
61         cout<<"Case #"<<Times<<": ";
62         topsort();
63 
64     }
65     return 0;
66 }

View Code

顺便记两个拓扑排序模板：

邻接矩阵：见本题

邻接表：

 1 邻接表建图： 
 2  32 void addedge(int x,int y)       //x->y
 3  33 {
 4  34     d[y]++;             //d[i]:点i的入度
 5  35     ev[cnt]=y;          //ev[i]:第i条边的destination
 6  36     nxt[cnt]=head[x];   //nxt[i]:第i条边的下一条边
 7  37     head[x]=cnt;        //head[i]:由i节点出发的第一条边的序号
 8  38     cnt++;
 9  39 }
10 
11 --------------------------------------------------------------------------------
12 
13 void topsort()
14 {
15     vector<int> vec;
16     for(int i=1; i<=N; i++)
17         if(d[i]==0)     vec.push_back(i);
18     for(int i=0; i<vec.size(); i++)
19     {
20         int x=vec[i];
21         for(int j=head[x]; j!=0; j=nxt[j])
22         {
23             int y=ev[j];
24             d[y]--;
25             if(d[y]==0)     vec.push_back(y);
26         }
27     }
28     int last=vec.size();
29     //last!=N说明有环
30 }
31 如果嫌慢可以把vector改写成普通数组

View Code

//PS：Reference的那个博主是地大的本科生，本科毕业就拿到了人人+去哪儿offer，orz