[tarjan+dfs]poj 2762 Going from u to v or from v to u？

テーマリンク:
http://poj.org/problem?id=2762
Going from u to v or from v to u？
Time Limit: 2000 MS
 
メモリLimit: 65536 K
Total Submissions: 14546
 
Acceepted: 3837
Description
In order to make their son braave，Jiajia and Wind Tae them to a big cave.The cave has n rooms，and one-way coridors connecting some rooms.Each time，Wind chose tworooms x x and y，and ask the the the gogogogotototototototototototototototototonit the gogogogogogogogogogotototototototototototototototototototototototototototototototototototototototototototototototototototototototototototototototototototaskys are all possible、but she actually doesn't know how to decide if a task is possible.To make here life ease，Jiajia decided to chose a cave in which eve pair of rooms is a possible.Given cave，cave，cantable Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan Japan atcanit？
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 coridors in the cave.The next m line s each contions two integers and v、indicating the corectur corr contra 
Output
The output shout contain T lines.Write'Yes'if the cave has the property stated above，or'No'otherswise.
Sample Input

1
3 3
1 2
2 3
3 1

Sample Output

Yes

Source
POJ Monthly-20.02.26,zgl&twb
[Submit]   [Go Back]   [Sttus]   ［ディスク］
タイトルの意味：
一枚の図をあげて、任意の2点vを判断して、uが到達できるかどうかを判断します。
問題解決の考え方：
タバサ+dfs
まず図に向かって強い連結成分があることを求めて、それから図を縮小して建設して、統計の入度の0の聯通の成分の個数、1を上回ってきっと駄目です。それから、子樹dfsを検索します。もしあるノードに息子が一人を超えると、この二人の息子の間には到着できません。だめです。
コード:

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 1100

int low[Maxn],dfn[Maxn],sc,bc,sta[Maxn];
int n,m,dep,dei[Maxn],in[Maxn];
bool iss[Maxn];
vector<vector<int> >myv;
vector<vector<int> >tree;
bool hae[Maxn][Maxn];
int ans;

void tarjan(int cur)
{
    int ne;
    low[cur]=dfn[cur]=++dep;
    sta[++sc]=cur;
    iss[cur]=true;

    for(int i=0;i<myv[cur].size();i++)
    {
        ne=myv[cur][i];
        if(!dfn[ne])
        {
            tarjan(ne);
            if(low[ne]<low[cur])
                low[cur]=low[ne];
        }
        else if(iss[ne]&&dfn[ne]<low[cur])
            low[cur]=dfn[ne];
    }
    if(low[cur]==dfn[cur])
    {
        ++bc;
        do
        {
            ne=sta[sc--];
            iss[ne]=false;
            in[ne]=bc;
        }while(ne!=cur);
    }
}
void solve()
{
    dep=sc=bc=0;
    memset(iss,false,sizeof(iss));
    memset(dfn,0,sizeof(dfn));

    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
}
void dfs(int cur)
{
    if(ans>2)
        return ;
    int res=0;

    for(int i=0;i<tree[cur].size();i++)
    {
        int ne=tree[cur][i];
        res++;
        dfs(ne);
    }
    if(res>=2)
        ans=INF;
}
int main()
{
    //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);

   int t;

   scanf("%d",&t);
   while(t--)
   {
       scanf("%d%d",&n,&m);
       myv.clear();
       myv.resize(n+1);
       memset(dei,0,sizeof(dei));
       for(int i=1;i<=m;i++)
       {
           int a,b;
           scanf("%d%d",&a,&b);
           myv[a].push_back(b);
       }
       solve();
       tree.clear();
       tree.resize(bc+1);
       memset(hae,false,sizeof(hae));
       for(int i=1;i<=n;i++)
       {
           for(int j=0;j<myv[i].size();j++)
           {
               int ne=myv[i][j];
               if(in[i]!=in[ne])
               {
                   dei[in[ne]]++;
                   if(!hae[in[i]][in[ne]])
                   {
                       hae[in[i]][in[ne]]=true;
                       tree[in[i]].push_back(in[ne]);
                   }
               }

           }
       }
       ans=0;
       for(int i=1;i<=bc;i++)
            if(!dei[i])
            {
                ans++;
                dfs(i);
                if(ans>1)
                    break;
            }

       if(ans==1)
            printf("Yes
");
       else
            printf("No
");
   }
    return 0;
}