80分TLE2和4 大佬求助P1892 [BOI2003]团伙
  • 板块题目总版
  • 楼主Muzzlex
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/3/5 15:01
  • 上次更新2023/10/28 07:14:49
查看原帖
80分TLE2和4 大佬求助P1892 [BOI2003]团伙
464368
Muzzlex楼主2022/3/5 15:01
#include<bits/stdc++.h>
using namespace std;
int s,n,m,f[2500];
bool g[1005][1005]; 
int find(int x)
{
    if(f[x]!=x)f[x]=find(f[x]); 
    return f[x];
}
void check()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(g[j][k]&&g[i][k])f[find(i)]=find(j);
			}
		}
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
	{
        f[i]=i;
    }
    for(int i=1;i<=m;i++)
	{
		char e;
		int x,y;
        cin>>e>>x>>y;
        if(e=='F')
		{
            f[find(x)]=find(y);
        }
		else
		{ 
            g[x][y]=true; 
            g[y][x]=true;
        }
    }
    check();
    for(int i=1;i<=n;i++)
	{
        if(f[i]==i)s++;
    }
    cout<<s;
}
2022/3/5 15:01
加载中...