悬关求条样例
查看原帖
悬关求条样例
637788
kimi0705楼主2023/10/7 19:22
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, x, cnt, ans;
int du[N];
bool Edge[N][N];
bool vis[N], flag;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
            vis[j] = 0;
        scanf("%d", &x);
        vector<int> V;
        V.resize(x);    
        for (int &j : V)
            scanf("%d", &j), vis[j] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
                for (int k : V)
                    du[j] += 1 - Edge[j][k], Edge[j][k] = 1;
    }
    cnt = n;
    for (int j = 1; j <= n; j++)
        vis[j] = 0;
    flag = true;
    while (flag)
    {
        flag = false;
        vector<int> V;
        for (int i = 1; i <= n; i++)
            if (du[i] == 0 && !vis[i])
            {
                V.push_back(i), vis[i] = 1, cnt--;
            }
        flag = V.size();
        for (int i : V)
            for (int j = 1; j <= n; j++) {
                du[j] -= Edge[i][j];
            }
        ans++;
    }
    cout << ans - 1;
}
2023/10/7 19:22
加载中...