2013通化招待試合C題D-City(そして検索集)


タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=4496
本当に弱すぎます....通化招待試合はこのコースだけです.やはり集水問題を調べます.
何も言いません.題目の前を後回しにして、後から前に加えればいいです.そして、テンプレートを調べました.
コードは以下の通りです
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>

using namespace std;
const int MAXN=11000, MAXM=110000;
int bin[MAXN], line1[MAXM], line2[MAXM], ans[MAXM];
int find1(int x)
{
    return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void merge1(int x, int y)
{
    int f1, f2;
    f1=find1(x);
    f2=find1(y);
    if(f2>f1)
        bin[f2]=f1;
    else
        bin[f1]=f2;
}
int main()
{
    int n, m, i, j, u, v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1; i<=n; i++)
            bin[i]=i;
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            line1[i]=u;
            line2[i]=v;
        }
        ans[m]=n;
        for(i=m-1; i>=0; i--)
        {
            if(find1(line1[i])!=find1(line2[i]))
            {
                ans[i]=ans[i+1]-1;
                merge1(line1[i],line2[i]);
            }
            else
            {
                ans[i]=ans[i+1];
            }
        }
        for(i=1; i<=m; i++)
            printf("%d
",ans[i]); } return 0; }