poj 2762 Going from u to v or from v to u? （强连通+缩点+拓扑排序求解单项连通） - c++编程基础

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 13343		Accepted: 3477

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

Source

POJ Monthly--2006.02.26,zgl & twb

题意：

给你一个图，判断这个图是否满足单项连通性。

思路：

强连通的点可以看做一个点（强连通缩点），重新构图后需满足有一条链将点串起来，于是拓扑排序，要满足前一个点与后一个点有边，代码写的有点挫。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 1005 #define MAXN 100005 #define mod 1000000007 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 0.000001 typedef long long ll; using namespace std; int n,m,ans,cnt,tot,flag; int cxx,lev,nn; int head[maxn],pre[maxn]; int dfn[maxn],low[maxn]; int sta[maxn],vis[maxn],vv[maxn],app[maxn]; struct Node { int v,next; } edge[MAXN]; vector
             
              Edge[maxn]; int mst[maxn][maxn]; int xx[MAXN],yy[MAXN],in[maxn]; void addedge(int u,int v) { cnt++; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt; } void dfs(int u) { // printf("%d->",u); int i,j,t; low[u]=dfn[u]=++lev; sta[++cxx]=u; vv[u]=1; for(i=head[u]; i; i=edge[i].next) { int v=edge[i].v; if(app[v]) continue ; if(vis[v]) { if(vv[v]) low[u]=min(low[u],dfn[v]); // 回边 } else { vis[v]=1; dfs(v); low[u]=min(low[u],low[v]); } } if(dfn[u]==low[u]) // 栈中u之后为强联通分量 缩点 纪录每个点缩之后为哪个点 { nn++; // printf("nn:%d\n",nn); int v=sta[cxx]; while(v!=u) { vv[v]=0; app[v]=1; pre[v]=nn; // printf("%d ",v); cxx--; v=sta[cxx]; } vv[v]=0; app[v]=1; // printf("%d\n",v); pre[v]=nn; cxx--; } } void topsort() { int i,j,t,u,v,last=0; queue
              
               q; for(i=1; i<=nn; i++) { if(in[i]==0) q.push(i); } while(!q.empty()) { u=q.front(); q.pop(); if(last&&!mst[last][u]) // 上一个到这一个必须有边 { flag=0; return ; } for(i=0; i