每日一道思维题——CF1761C - Set Construction

题意：

存在一个n×n的01矩阵(i,j)处值为1代表A_i 是 A_j的真子集,求出这个集合A

思路：

我们在一开始的时候将每个位置赋初值，若i处的值是j的真子集将i处的值赋值给j

代码：

#include <iostream>
#include <set>
using namespace std;
 
const int N = 1010;
 
int n;
char b[N][N];
 
void solve()
{
    set<int> se[N];
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            cin >> b[i][j];
            se[i].insert(i);
        }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(b[i][j] == '1')
            {
                for(auto t: se[i])
                {
                    se[j].insert(t);
                }
            }
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(b[i][j] == '1')
            {
                for(auto t: se[i])
                {
                    se[j].insert(t);
                }
            }
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        cout << se[i].size() << ' ';
        for(auto t: se[i])
            cout << t << ' ';
        cout << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}