[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

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 using namespace std;

 const int maxn=;

 vector<int>G[maxn];

 vector<int>rG[maxn];

 vector<int>vs;

 int vis[maxn];

 int cmp[maxn];

 int last[maxn];

 int deg[maxn];

 int next[maxn];

 int V;

 vector<int>vc[maxn];

 void add_edge(int u,int v)

 {

     G[u].push_back(v);

     rG[v].push_back(u);

 }

 void init(int n)

 {

     for(int i=;i<n;i++)

     {

         G[i].clear();

         rG[i].clear();

         vc[i].clear();

         vis[i]=;

         last[i]=-;

         deg[i]=;

         next[i]=-;

     }

 }

 void dfs(int v)

 {

     vis[v]=;

     for(int i=;i<G[v].size();i++)

     {

         if(!vis[G[v][i]])dfs(G[v][i]);

     }

     vs.push_back(v);

 }

 void rdfs(int v,int k)

 {

     vis[v]=;

     cmp[v]=k;

     vc[k].push_back(v);

     for(int i=;i<rG[v].size();i++)

     {

         if(!vis[rG[v][i]])rdfs(rG[v][i],k);

     }

 }

 int scc()

 {

     memset(vis,,sizeof(vis));

     vs.clear();

     for(int i=;i<V;i++)

     {

         if(!vis[i])dfs(i);

     }

     memset(vis,,sizeof(vis));

     int k=;

     for(int i=vs.size()-;i>=;i--)

     {

         if(!vis[vs[i]])rdfs(vs[i],k++);

     }

     return k;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     int t;

     cin>>t;

     while(t--)

     {

         int n,m;

         cin>>n>>m;

         V=n;

         init(n);

         int u,v;

         for(int i=;i<m;i++)

         {

             cin>>u>>v;

             add_edge(--u,--v);

         }

         int k=scc();

         memset(vis,,sizeof(vis));

         int flag=;

         int num=;

         for(int i=;i<k;i++)

         {

             for(int j=;j<vc[i].size();j++)

             {

                 u=vc[i][j];

                 for(int l=;l<G[u].size();l++)

                 {

                     v=G[u][l];

                     if(cmp[u]!=cmp[v])

                     {

                         if(last[cmp[v]]==-)

                         {

                             last[cmp[v]]=cmp[u];

                         }

                         else if(last[cmp[v]]==cmp[u])continue;

                         else flag=;

                         if(next[cmp[u]]==-)

                         {

                             next[cmp[u]]=cmp[v];

                         }

                         else if(next[cmp[u]]==cmp[v])

                         {

                             continue;

                         }

                         else flag=;

                     }

                 }

             }

         }

         for(int i=;i<k;i++)

         {

             if(last[i]==-)num++;

         }

         if(flag&&num==)cout<<"Yes"<<endl;

         else cout<<"No"<<endl;

     }

     return ;

 }

代码君

巴特西

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

最新文章

热门文章