《论为什么最后一个测试点超时,运行两分钟》
查看原帖
《论为什么最后一个测试点超时,运行两分钟》
406258
Jay20081229楼主2022/2/10 18:25

@niuhong

这是我的代码,麻烦您帮我看一下:

#include<cstdio>
#include<cstring>
using namespace std;
bool lj[102][102];
bool ans[102] = {};
int ans1 = 0;
int tmp = 0;
int n, m;
bool v[102] = {};
int s[102] = {0};
int van[102];//节点遍历录
int cnt;

void dfs(int st) {
    if(s[st] < ans1 - 1) return;
    for(int i = 1; i <= cnt; i++) {
        if(not(lj[st][van[i]])) {
            v[st] = false;
            return;
        }
    }
    if(cnt > ans1) {
        ans1 = cnt;
        for(int i = 1; i <= n; i++) {
            ans[i] = v[i];
        }
    }
    van[cnt + 1] = st;
    for(int i = 1; i <= n; i++) {
        if(lj[st][i] && i != st) {
            if(v[i]) continue;
            v[i] = true;
            cnt++;
            dfs(i);
            cnt--;
            v[i] = false;
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    memset(lj, true, sizeof(lj));
    for(int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        s[a]++;
        s[b]++;
        lj[a][b] = false;
        lj[b][a] = false;
    }
    for(int i = 1; i <= n; i++) {
        memset(v, false, sizeof(v));
    	cnt = 0;
    	v[i] = true;
    	if(s[i] < tmp) continue;
    	dfs(i);
    	if(ans1 + 1 > tmp) tmp = ans1 + 1;
    	//v[i] = false;
    }
    printf("%d\n", ans1 + 1);
    for(int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}
2022/2/10 18:25
加载中...