[poj2762] Going from u to v or from v to u?(Kosaraju缩点+拓排)

转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud

Going from u to v or from v to u?

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 14778		Accepted: 3911

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases.

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

Sample Output

Yes

题意：给一个图，问是否为单向连通。

Kosaraju+缩点，然后拓扑序搞一下，若只有一条没有分支的链，则Yes,否则No

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <vector>
  5 using namespace std;
  6 const int maxn=1010;
  7 vector<int>G[maxn];
  8 vector<int>rG[maxn];
  9 vector<int>vs;
 10 int vis[maxn];
 11 int cmp[maxn];
 12 int last[maxn];
 13 int deg[maxn];
 14 int next[maxn];
 15 int V;
 16 vector<int>vc[maxn];
 17 void add_edge(int u,int v)
 18 {
 19     G[u].push_back(v);
 20     rG[v].push_back(u);
 21 }
 22 void init(int n)
 23 {
 24     for(int i=0;i<n;i++)
 25     {
 26         G[i].clear();
 27         rG[i].clear();
 28         vc[i].clear();
 29         vis[i]=0;
 30         last[i]=-1;
 31         deg[i]=0;
 32         next[i]=-1;
 33     }
 34 }
 35 void dfs(int v)
 36 {
 37     vis[v]=1;
 38     for(int i=0;i<G[v].size();i++)
 39     {
 40         if(!vis[G[v][i]])dfs(G[v][i]);
 41     }
 42     vs.push_back(v);
 43 }
 44 void rdfs(int v,int k)
 45 {
 46     vis[v]=1;
 47     cmp[v]=k;
 48     vc[k].push_back(v);
 49     for(int i=0;i<rG[v].size();i++)
 50     {
 51         if(!vis[rG[v][i]])rdfs(rG[v][i],k);
 52     }
 53 }
 54 int scc()
 55 {
 56     memset(vis,0,sizeof(vis));
 57     vs.clear();
 58     for(int i=0;i<V;i++)
 59     {
 60         if(!vis[i])dfs(i);
 61     }
 62     memset(vis,0,sizeof(vis));
 63     int k=0;
 64     for(int i=vs.size()-1;i>=0;i--)
 65     {
 66         if(!vis[vs[i]])rdfs(vs[i],k++);
 67     }
 68     return k;
 69 }
 70 int main()
 71 {
 72     ios::sync_with_stdio(false);
 73     int t;
 74     cin>>t;
 75     while(t--)
 76     {
 77         int n,m;
 78         cin>>n>>m;
 79         V=n;
 80         init(n);
 81         int u,v;
 82         for(int i=0;i<m;i++)
 83         {
 84             cin>>u>>v;
 85             add_edge(--u,--v);
 86         }
 87         int k=scc();
 88         memset(vis,0,sizeof(vis));
 89         int flag=1;
 90         int num=0;
 91         for(int i=0;i<k;i++)
 92         {
 93             for(int j=0;j<vc[i].size();j++)
 94             {
 95                 u=vc[i][j];
 96                 for(int l=0;l<G[u].size();l++)
 97                 {
 98                     v=G[u][l];
 99                     if(cmp[u]!=cmp[v])
100                     {
101                         if(last[cmp[v]]==-1)
102                         {
103                             last[cmp[v]]=cmp[u];
104                         }
105                         else if(last[cmp[v]]==cmp[u])continue;
106                         else flag=0;
107                         if(next[cmp[u]]==-1)
108                         {
109                             next[cmp[u]]=cmp[v];
110                         }
111                         else if(next[cmp[u]]==cmp[v])
112                         {
113                             continue;
114                         }
115                         else flag=0;
116                     }
117                 }
118             }
119         }
120         for(int i=0;i<k;i++)
121         {
122             if(last[i]==-1)num++;
123         }
124         if(flag&&num==1)cout<<"Yes"<<endl;
125         else cout<<"No"<<endl;
126     }
127 
128     return 0;
129 }

代码君