1213 how many tables.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 74 行

/*
1213 How Many Tables
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
#include <iostream>
using namespace std;

const int Max=1000;

int changeTables(int from,int to,int frinds[])
{
    int i;
    for(i=0;i<=Max;i++)
    {
        if(frinds[i]==from)
            frinds[i]=to;
        if(frinds[i]>from)
            frinds[i]--;
    }
    return 1;
}

int main()
{
    int t,n,a,b,m,ca,cb,tables;
    int frinds[Max+1];
    cin>>t;
    for(ca=0;ca<t;ca++)
    {
        for(cb=0;cb<=Max;cb++)
            frinds[cb]=0;
        cin>>n>>m;
        tables=0;
        for(cb=0;cb<m;cb++)
        {
            cin>>a>>b;
            if(frinds[a]==0 && frinds[b]==0)//两者都还没安排
            {
                tables++;
                frinds[a]=frinds[b]=tables;
            }
            else
            {
                if(frinds[a]!=0 && frinds[b]!=0) //两位都安排了
                {
                    if(frinds[a]!=frinds[b])//且两位位置不同
                    {
                        tables--;
                        frinds[a]>frinds[b] ? changeTables(frinds[a],frinds[b],frinds) : changeTables(frinds[b],frinds[a],frinds) ;
                    }
                }//if
                else//其中一位安排了
                {
                    if(frinds[a]!=0)
                        frinds[b]=frinds[a];
                    else
                        frinds[a]=frinds[b];
                }
            }

        }//for cb
        
        for(cb=1;cb<=n;cb++)
            if(frinds[cb]==0)//还有未安排的，彼此都不熟悉
                tables++;
        
        cout<<tables<<endl;
    }
    return 0;
}