程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2762 Going from u to v or from v to u? （強連通+縮點+拓撲排序求解

poj 2762 Going from u to v or from v to u? （強連通+縮點+拓撲排序求解

編輯：C++入門知識

Going from u to v or from v to u? 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];
vectorEdge[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;
    queueq;
    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