首页 > 代码库 > poj 2762 Going from u to v or from v to u?

poj 2762 Going from u to v or from v to u?

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 17689 Accepted: 4745

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

13 31 22 33 1

Sample Output

Yes

Source

POJ Monthly--2006.02.26,zgl & twb
 
题目大意

给出一些点,和他们之间的有向边,如果图中任意两点 x,y 之间满足 x 可以到达 y 或者 y 可以到达 x ,就输出“Yes”,否则输出“No”

 

因为n>1000 所以挨个判断是不可取的 

所以我们用tarjan 求出强连通分量的个数

然后判断这几个强连通分量在不在一条链上就可以了 

tarjan缩点+拓扑排序

屠龙宝刀点击就送

#include <cstring>#include <ctype.h>#include <cstdio>#include <queue>#define M 6005#define N 1500using namespace std;void read(int &x){    x=0;bool f=0;    char ch=getchar();    while(!isdigit(ch))    {        if(ch==-) f=1;        ch=getchar();    }    while(isdigit(ch))    {        x=x*10+ch-0;        ch=getchar();    }    x=f?(~x)+1:x;}int in[N],g[N][N],tim,dfn[N],col[N],sumcol,low[N],T,n,m,head[N],cnt,stack[N],top;bool instack[N],vis[N];struct node{    int next,to;}edge[M];void add(int u,int v){    edge[++cnt].next=head[u];    edge[cnt].to=v;    head[u]=cnt;}int min(int a,int b){    return a>b?b:a;}void dfs(int x){    stack[++top]=x;    instack[x]=1;    vis[x]=1;    low[x]=dfn[x]=++tim;    for(int i=head[x];i;i=edge[i].next)    {        int v=edge[i].to;        if(instack[v]) low[x]=min(low[x],dfn[v]);        else if(!vis[v])        {            dfs(v);            low[x]=min(low[x],low[v]);        }    }    if(low[x]==dfn[x])    {        sumcol++;        while(x!=stack[top])        {            instack[stack[top]]=0;            col[stack[top--]]=sumcol;        }        instack[stack[top]]=0;        col[stack[top--]]=sumcol;    }}bool judge(){    queue<int>q;    for(int i=1;i<=sumcol;i++)    if(!in[i]) q.push(i);    if(q.size()>1) return false;    while(!q.empty())    {        int now=q.front();        q.pop();        for(int i=1;i<=sumcol;i++)        if(g[now][i])        {            in[i]--;            if(!in[i]) q.push(i);        }        if(q.size()>1) return false;    }    return true;}int main(){    read(T);    for(;T--;)    {        memset(head,0,sizeof(head));        memset(dfn,0,sizeof(dfn));        memset(vis,0,sizeof(vis));        memset(instack,0,sizeof(instack));        memset(col,0,sizeof(col));        memset(low,0,sizeof(low));        memset(in,0,sizeof(in));        memset(g,0,sizeof(g));         tim=0;top=0;sumcol=0;cnt=0;        bool f=false;        read(n);        read(m);        for(int x,y,i=1;i<=m;i++)        {            read(x);            read(y);            add(x,y);        }        for(int i=1;i<=n;i++)        if(!vis[i]) dfs(i);        if(sumcol==1) {printf("Yes\n");continue;}        for(int i=1;i<=n;i++)        {            for(int j=head[i];j;j=edge[j].next)            {                int v=edge[j].to;                if(i!=v&&col[i]!=col[v])                {                    g[col[i]][col[v]]=1;                    in[col[v]]++;                }            }        }        if(judge()) printf("Yes\n");        else printf("No\n");    }    return 0;}

 

poj 2762 Going from u to v or from v to u?