1487. Chinese Football 夜

http://acm.timus.ru/problem.aspx?space=1&num=1487

A可以打赢了B并不代表A打得比B好  stronger！=better

注意这句话：Denis claims that the “Katraps” team plays better than the “Kolomotiv” team,
namely, that “Katraps” is not weaker than any team which is stronger than
“Komolotiv”.

所以 如果A和B有共同祖先 No 否则 YES

自己写的程序时间复杂度很高 水过

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
#define LL long long
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const double eps=1e-9;
const int INF=0x3f3f3f3f;
const double FINF=1e12;
const int N=1005;
int head[N],I;
struct node
{
    int j,next;
}edge[N*N];
char c[N][N];
//bool root[N];
bool visited[N];
//vector<int>vt;
void add(int i,int j)
{
    edge[I].j=j;
    edge[I].next=head[i];
    head[i]=I++;
}
void dfs(int x,int l)
{
    visited[x]=true;
    for(int t=head[x];t!=-1;t=edge[t].next)
    {
        int j=edge[t].j;
        if(!visited[j])
        {c[l][j]='1';dfs(j,l);}
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    memset(head,-1,sizeof(head));
    I=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    {
        cin>>c[i][j];
        if(c[i][j]=='1')
        add(i,j);
    }
    for(int i=1;i<=n;++i)
    {
        memset(visited,false,sizeof(visited));
        dfs(i,i);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        bool flag=true;
        for(int i=1;i<=n;++i)
        if(c[i][l]=='1'&&c[i][r]=='1')
        {flag=false;break;}
        if(flag==true)
        cout<<"YES"<<endl;
        else
        cout<<"No"<<endl;
    }
    return 0;
}