萌新刚学缩点,CF上交了几页了
  • 板块灌水区
  • 楼主Six_chestnuts
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/10 18:32
  • 上次更新2024/11/10 21:03:29
查看原帖
萌新刚学缩点,CF上交了几页了
838514
Six_chestnuts楼主2024/11/10 18:32

CF1761E

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e3+5;
int n,tot,fa[N],sz[N],dfn[N],low[N];
vector<int> nbr[N];
bool cut[N];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
	x=find(x),y=find(y);
	if(x!=y)
		fa[x]=y,sz[y]+=sz[x];
}
void Tarjan(int cur,int root)
{
	dfn[cur]=low[cur]=++tot;
	int son=0;
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i];
		if(!dfn[nxt])
		{
			Tarjan(nxt,root);
			low[cur]=min(low[cur],low[nxt]);
			son++;
			if(dfn[cur]<=low[nxt]&&(cur!=root||son>=2))
				cut[cur]=1;
		}
		else
			low[cur]=min(low[cur],dfn[nxt]);
	}
}
void work()
{
	cin>>n;
	memset(cut,0,sizeof(cut));
	tot=0;
	for(int i=1;i<=n;i++)
		fa[i]=i,sz[i]=1,nbr[i].clear();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			char flag;
			cin>>flag;
			if(flag=='1')
				nbr[i].push_back(j),unionn(i,j);
		}
	int cnt=0,f=0;
	sz[0]=1e18;
	for(int i=1;i<=n;i++)
	{
		if(find(i)==i)
		{
			cnt++;
			if(sz[i]<sz[f])
				f=i;
		}
		if(!dfn[i])
			Tarjan(i,i);
//		cout<<sz[i]<<" ";
	}
	if(cnt==1)
	{
		cout<<"0\n";
		return ;
	}
	for(int i=1;i<=n;i++)
		if(nbr[i].size()!=sz[find(i)]-1&&!cut[i])
		{
			cout<<"1\n"<<i<<"\n";
			return ;
		}
	if(cnt>2&&sz[f]>1)
	{
		cout<<"2\n1";
		for(int i=1;i<=n;i++)
			if(find(i)!=find(1))
			{
				cout<<" "<<i<<"\n";
				return ;
			}
		return ;
	}
	cout<<sz[f]<<"\n";
	for(int i=1;i<=n;i++)
		if(find(i)==f)
			cout<<i<<" ";
	cout<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("as01.in","r",stdin);
//	freopen("as01.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
		work(); 
	return 0;
}
2024/11/10 18:32
加载中...