拓扑序列 + dfs + 读题

这个题感觉很坑，光题面上就有一个地方没说明白； 先建图判一下拓扑序列，合法的话就对每个点进行爆搜。搜下大于它的点的个数和小于它的点的个数，都小于(n + 1) / 2就输出1， 否则输出0； 坑点1：dfs搜的时候必须判断这个点有没有在本次搜过，否则会tle 坑点2：注意审题

using namespace std;

const int N = 110;

vector<int> g[N], gg[N];
int d[N];
int n, m;
bool st1[N], st2[N];

bool bfs() {
    queue<int> q;
    int cnt = 0;
    for(int i = 1; i <= n; i ++ )
        if(d[i] == 0) q.push(i), cnt ++;
        
    
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        for(auto it : g[t]) {
            d[it] --;
            if(d[it] == 0) {
                q.push(it);
                cnt ++;
            }
        }
    }
    
    if(cnt == n) return true;
    else return false;
}


int ddfs(int u) {
    int cnt = 0;
    st1[u] = 1;
    for(int v : g[u]) {
        if(!st1[v]) {
            cnt += ddfs(v) + 1;
        }
    }
    
    return cnt;
}

int udfs(int u) {
    int cnt = 0;
    st2[u] = 1;
    for(int v : gg[u]) {
        if(!st2[v]) {
            cnt += udfs(v) + 1;
        }
    }
    
    return cnt;
}

int main()
{
    int T;
    scanf("%d", &T);
    
    while(T -- ) {
        
        scanf("%d%d", &n, &m);
        
        for(int i = 1; i <= n; i ++ ) g[i].clear(), d[i] = 0, gg[i].clear();
        
        while(m -- ) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a].push_back(b);
            gg[b].push_back(a);
            d[b] ++;
        }
        
        bool has = bfs();
        //cout << has << endl;
        if(has) {
            
            for(int i = 1; i <= n; i ++ ) {
                memset(st1, 0, sizeof st1), memset(st2, 0, sizeof st2);
                if(udfs(i) <= n / 2 && ddfs(i) <= n / 2) {
                    putchar('1');
                }
                else putchar('0');
            }
        }
        else {
            for(int i = 1; i <= n; i ++ ) putchar('0');
        }
        
        putchar('\n');
    }
    
    return 0;
}