poj2762 强连通分量缩点+判断出度与入度

短命女 2022-08-20 06:16 153阅读 0赞

Going from u to v or from v to u?

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 16086</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 4282</td> 
  </tr> 
 </tbody> 
</table>

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

1
    3 3
    1 2
    2 3
    3 1

Sample Output

Yes

题意: 判断所给定的有向图是否满足任意两点u和v, 总是存在u到v的路径**或者**存在v到u的路径.

分析:开始并没有注意到是"或者", 认为是"并且"了, wrong了好多. ..

先把原图进行缩点, 这样图就会变成一个DAG(有向无环图), 统计每个分块的入度跟出度, 如果有两个分块入度都为零, 那么他们不能相互到达, 出度同理.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1001;
    vector<int> G[N];
    int n,m,low[N],dfn[N],scc[N],cnt,dfs_num,top,Stack[N];
    bool rd[N],cd[N];
    
    void init()
    {
        for(int i=0;i<=n;i++) //
        {
            G[i].clear();
        }
        mem(dfn,0);
        mem(scc,0);
        mem(rd,0);
        mem(cd,0);
        top=0;
        dfs_num=0;
        cnt=0;
    }
    
    void tarjan(int x)
    {
        low[x] = dfn[x] = ++dfs_num;
        Stack[++top]=x;
        for(int i=0;i<G[x].size();i++)
        {
            int t=G[x][i];
            if(!dfn[t])
            {
                tarjan(t);
                low[x]=min(low[x],low[t]);
            }
            else if(!scc[t])
            {
                low[x] = min(low[x],dfn[t]);
            }
        }
        if(dfn[x] == low[x])
        {
            cnt++;
            while(1)
            {
                int t = Stack[top--];
                scc[t] = cnt;
                if(x==t) break;
            }
        }
    }
    int main()
    {
        int T=in();
        while(T--)
        {
            n=in(),m=in();
            init();
            for(int i=0;i<m;i++)
            {
                int x=in(),y=in();
                G[x].push_back(y);
            }
            for(int i=1;i<=n;i++)
            {
                if(!dfn[i])
                {
                    tarjan(i);
                }
            }
            if(cnt==1)   //n==1的时候是Yes,坑
            {
                puts("Yes");
                continue;
            }
            for(int i=1;i<=n;i++) //
            {
                int x=scc[i];
                for(int j=0;j<G[i].size();j++)
                {
                    int y=scc[G[i][j]];
                    if(x == y) continue;
                    rd[y]=1;
                    cd[x]=1;
                }
            }
            bool yes=1;
            int c=0,c1=0;
            for(int i=1;i<=cnt;i++)
            {
                if(!rd[i])  //入度为0的大于1个就不行
                {
                    c++;
                    if(c>=2)
                    {
                        yes=0;
                        break;
                    }
                }
                if(!cd[i])//出度为0的大于1个也不行
                {
                    c1++;
                    if(c1>=2)
                    {
                        yes=0;
                        break;
                    }
                }
            }
            puts(yes?"Yes":"No");
        }
        return 0;
    }