【构造】CF1761 E

缺乏、安全感 2024-03-23 22:53 78阅读 0赞

[Problem - 1761E - Codeforces][]

题意：  
![0622cda9a5a44fcfbb3df51c5babd8bc.png][]

思路：

![a77bf2c641564be1806f17f3667128e0.png][]

Code：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    void solve() {
        int n;
        std::cin >> n;
        
        std::vector g(n, std::vector<int>(n));
        std::vector<int> deg(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char x;
                std::cin >> x;
                g[i][j] = x - '0';
                deg[i] += g[i][j];
            }
        }
        
        std::vector<std::vector<int>> comp;
        
        std::vector<int> vis(n);
        
        for (int i = 0; i < n; i++) {
            if (vis[i]) {
                continue;
            }
            
            std::vector<int> q;
            q.push_back(i);
            vis[i] = 1;
            
            for (int i = 0; i < int(q.size()); i++) {
                int x = q[i];
                
                for (int y = 0; y < n; y++) {
                    if (g[x][y] && !vis[y]) {
                        q.push_back(y);
                        vis[y] = 1;
                    }
                }
            }
            
            comp.push_back(q);
        }
        
        //第一种情况，只有一个连通分量
        if (comp.size() == 1) {
            std::cout << 0 << "\n";
            return;
        }
        
        for (auto s : comp) {
            //第二种情况，存在一个孤立点
            if (s.size() == 1) {
                std::cout << 1 << "\n";
                std::cout << s[0] + 1 << "\n";
                return;
            }
            //第三种情况，存在一个图为不完全图
            if (deg[s.back()] != int(s.size()) - 1) {
                std::cout << 1 << "\n";
                std::cout << s.back() + 1 << "\n";
                return;
            }
            for (auto x : s) {
                if (deg[x] != int(s.size()) - 1) {
                    std::cout << 1 << "\n";
                    std::cout << x + 1 << "\n";
                    return;
                }
            }
        }
        //第四种情况，存在大于两个完全图
        if (comp.size() > 2) {
            std::cout << 2 << "\n";
            std::cout << comp[0][0] + 1 << " " << comp[1][0] + 1 << "\n";
            return;
        }
        //剩下的情况，只有两个完全图
        if (comp[0].size() > comp[1].size()) {
            std::swap(comp[0], comp[1]);
        }
        
        std::cout << comp[0].size() << "\n";
        for (auto x : comp[0]) {
            std::cout << x + 1 << " \n"[x == comp[0].back()];
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t;
        std::cin >> t;
        
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - 1761E - Codeforces]: https://codeforces.com/problemset/problem/1761/E
[0622cda9a5a44fcfbb3df51c5babd8bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ff6fb8b75e224de7b4175ec90ac3f007.png
[a77bf2c641564be1806f17f3667128e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/172425a44a5148cebc7548ee6c69a3f1.png