CF1761E Make It Connected

· · 题解

如果你 TLE10 了，请使用较快的输入输出方式。
这题卡读入是我没想到的，可能很多人打出正解了然后被读入搞了一手。

题意：
给你很多个图，然后你每次可以选点，将与这个点相连的边删掉，把它没有连边的点连起来，问你最少步数，并输出方案。

题解：
其实是个结论题啊。。。
首先考虑如果是一个图，就是全部点联通了，那么就是 0。至于连通块怎么数你拿个并查集维护一下即可，或者 dfs 一遍全部点，就能判处所以连通块。

其次考虑如果存在一个大小为 1 的连通块，就是一个点为一个图，那么很显然就是只需要 1 的步数，就能把所有点联通了。

再想，如果有一个图不为完全图（即图中任意两点都有边），那么其实也只需要 1 步，就是找出度数最小的点，对它进行操作即可。
证明很简单，将与这个度数最小的点有关的边删去后，它现在就为单独的一点，然后把它和刚刚没有连过的所有点相连，那么其他连通块肯定可以连起来，而且因为不为完全图，且它度数最小，所以重连边的时候一定有边会连向它在原来的那个图的点。判断完全图的方法就是点数等于边数减一，那么这里只要不满足这一点即可，对于找度数最短的点，你依然可以通过 dfs ，那么最后 dfs 到的点，就是度数最小的点。

继续，如果有大于两个的连通块。其实也只需要两步就可以完成，随便找一个点进行操作，然后这个点会和其他连通块相连，但是和自己的连通块断开了，所以只需要再找一个另外的一个连通块上的点，进行操作，那么就可以将那个连通块联通回去了。
证明其实很好证明，第一次操作后，一定只有两个连通块，且与第一次选点组成的连通块一定不为完全图，其实就变为了上一个讨论的东西，且更特殊，不需要找度数最小的点，因为所有点都不可能和每个点相连，所以只需要随便找一个不为原来连通块的点即可。

最后一种情况，也是比较复杂的情况，需要贪心。剩下的这种情况其实就是两个完全图了。结论就是找较小的连通块，最小步数就是较小连通块的点数。
证明，不难发现，每次操作完之后只是相当于把一个点从一个连通块分割出去，到另一个连通块那里去了，剩下的还是两个完全图，改变的只是两个连通块点的数量，那么其实就只需要一直操作一个连通块，使其剩下一个点，再操作那个点即可。

大概就是分这五类，每种情况都有每种情况非常独特的性质，希望读者自己画一画图理解一下。
代码如下： 

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<functional>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;

inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0',c=getchar();}
    return x*f;
}
const int N=4010;
char a[N];
vector<int>v[N],ve;
int cnt,qt;
int dfn[N];
void dfs(int x)
{
    ve.push_back(x);
    dfn[x]=cnt;
    for(int i=0;i<v[x].size();i++)
    {
        int to=v[x][i];
        if(!dfn[to])dfs(to);
    }
}
void solve()
{
    int n=read();
    for(int i=1;i<=n;i++)v[i].clear(),dfn[i]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a+1);
        //string a;cin>>a;
        for(int j=1;j<=n;j++)
            if(a[j]=='1')v[i].push_back(j);
    }

    cnt=0,qt=-1;

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            cnt++;
            ve.clear();
            dfs(i);
            ll en=0;
            int si=ve.size();
            for(int j=0;j<si;j++)
                if(v[ve[j]].size()!=si-1)en=ve[j];
            if(en)qt=en;
            if(ve.size()==1)qt=i;
        }
    }
    if(cnt==1)
    {
        printf("0\n");
        return;
    }
    if(qt!=-1)
    {
        printf("1\n%d\n",qt);
        return;
    }
    if(cnt!=2)
    {
        printf("2\n1 ");
        for(int i=1;i<=n;i++)
        {
            if(dfn[i]!=dfn[1])
            {
                printf("%d\n",i);
                return;
            }
        }
    }
    int sum1=0,sum2=0;
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==dfn[1])sum1++;
        else sum2++;
    }
    printf("%d\n",min(sum1,sum2));

    if(sum1<sum2)
    {
        for(int i=1;i<=n;i++)
            if(dfn[i]==dfn[1])printf("%d ",i);
        printf("\n");
        return;
    }

    for(int i=1;i<=n;i++)
        if(dfn[i]!=dfn[1])printf("%d ",i);
    printf("\n");
}
int main()
{
    int T=read();
    while(T--)solve();
    return 0;
}