PTA 5 - 16 친구 권 (25 점) [병 찰 집]

2319 단어 병 찰 집사다리
5-16 친구 권   (25 분)
한 학교 에는 N 명의 학생 이 있어 M 개의 클럽 을 만 들 었 다.각 클럽 의 학생 들 은 어느 정도 비슷 한 취 미 를 가지 고 친구 권 을 형성한다.한 학생 은 여러 개의 다른 클럽 에 동시에 속 할 수 있다.'내 친구 의 친구 도 내 친구' 라 는 추론 에 따 르 면 A 와 B 가 친구 이 고 B 와 C 가 친구 라면 A 와 C 도 친구 라 는 것 을 알 수 있다.최대 친구 권 에 몇 명 이 있 는 지 계산 하 는 프로그램 을 만들어 보 세 요.
입력 형식:
입력 한 첫 줄 은 두 개의 정수 N (\ le ≤ 30000) 과 M (\ le ≤ 1000) 을 포함 하고 각각 학교의 학생 총수 와 클럽 의 개 수 를 대표 한다.뒤의 M 줄 은 각 줄 마다 다음 과 같은 형식 으로 1 개의 클럽 의 정 보 를 제공 하 는데 그 중에서 학생 들 은 1 ~ N 번호 에서 i Mi（ ） 1（ ） 2 … Mi
출력 형식:
출력 은 최대 친구 권 에 몇 명 이 있 는 지 를 나타 내 는 정 수 를 보 여 줍 니 다.
입력 예시:
7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

출력 예시:
4

팁: pre [] 를 먼저 sort 하면 max 를 쉽게 찾 을 수 있 습 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define rep(i,j,k)for(i=j;ik;i--)
#define MS(x,y)memset(x,y,sizeof(x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll long long
#define abs(x) (x>0?x:-x)
const int INF=0x7ffffff;
const ll MAX=1e18;

const int M=4e4;
int i,j,k,n,m;
int pre[M];

int f(int x){
  while(x!=pre[x])
    x=pre[x];
  return x;
}

int main()
{
    while(cin>>n>>m){
        for(i=0;i<=n;i++)pre[i]=i;
        for(i=1;i<=m;i++){
           int k;cin>>k;
           int b;cin>>b;
           k--;
           int xx=f(b);
           while(k--){
            int a;cin>>a;
            int yy=f(a);
            if(xx!=yy)pre[yy]=xx;
           }
        }
        for(i=1;i<=n;i++)pre[i]=f(i);
        int ans=0;int sum=1;
        sort(pre+1,pre+n+1);
        for(i=2;i<=n;i++){
            if(pre[i]==pre[i-1])sum++;
            else {
                ans=max(sum,ans);
                sum=1;
            }
        }
        cout<
POJ 1273 & & HDU 1532 Drainage Ditches (최대 흐름 - DINIC)
ZOJ 3735 Josephina and RPG DP

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage