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;
}