首页 > 代码库 > HDU 4496 D-City(并查集,逆思维)

HDU 4496 D-City(并查集,逆思维)

题目

 

熟能生巧。。。常做这类题,就不会忘记他的思路了。。。

 

//可以反过来用并查集,还是逐个加边,但是反过来输出。。。我是白痴。。。。、又没想到//G++能过,C++却wa,这个也好奇怪呀。。。#include<stdio.h>#include<string.h>int fx,fy,r,bin[10010];int x[100010],y[100010],n,m,i,count,ans[100010],j;int find(int x){        //改成这样就不会超时了么好奇怪为什么    if(bin[x] == x)return x;     return bin[x] = find(bin[x]);    /*超时到哭,,,why?     r=x;    while(bin[r]!=r)    {        r=bin[r];    }    return r;    */}void merge(int x,int y){    fx=find(x);    fy=find(y);    if(fx!=fy)    {        bin[fx]=fy;        ans[j]=ans[j-1]+1;    }    else        ans[j]=ans[j-1];    j++;}int main(){    while(scanf("%d %d",&n,&m)!=EOF)    {        memset(ans,0,sizeof(ans));        for(i=0;i<n;i++)        {            bin[i]=i;        }        for(i=0;i<m;i++)        {            scanf("%d %d",&x[i],&y[i]);        }        j=0;        for(i=m-1;i>=0;i--)        {            merge(x[i],y[i]);        }            for(i=j-2;i>=0;i--)            printf("%d\n",n-ans[i]);        printf("%d\n",n);    }    return 0;}
View Code