#include #include #include #include // Yukicoder №556 仁義なきサルたち ★★☆ // https://yukicoder.me/problems/no/556 // グループ人数つき Find tree // *********************** // for debug #define DEBUGs #define YUKICODER // ----------- #ifdef YUKICODER #define gc(c) do{c = getchar_unlocked();}while(0) #define pc(c) putchar_unlocked(c) extern char getchar_unlocked(void); extern void putchar_unlocked(char c); #else #define gc(c) do{c = getchar();}while(0) #define pc(c) putchar(c) #endif void out(int n) { // 整数の表示（出力） int i; char b[30]; if (!n) pc('0'); else { if (n < 0) pc('-'), n = -n; i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); } pc('\n'); } #define NOP do{}while(0) #ifdef DEBUG #define TRACE(...) do{printf(__VA_ARGS__);fflush(stdout);}while(0) #define TRACECR do{putchar_unlocked('\n');fflush(stdout);}while(0) #else #define TRACE(...) NOP #define TRACECR NOP #endif #define errmes(...) do{fprintf(stderr,__VA_ARGS__);}while(0) #define mypc(d) putchar_unlocked((int)(d)) #define PRINCR mypc('\n') #define NOCR(strig) do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0) // for stdio #define GETLINE(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0) #define GETINTS(a,b) {char s[34];int *ap=a;REP(i,b){GETWORD(s);*ap++=atoi(s);}} #define SWAP(type,a,b) do{type _c;_c=a;a=b;b=_c;}while(0) #define MAX(a,b) ((a)>(b)?(a):(b)) #define REP(a,b) for(int a=0;a<(int)(b);++a) #define REP1(a,b) for(int a=1;a<=(int)(b);++a) #define Possible(a) printf("%s",((a)?"Possible":"Impossible")) #define possible(a) printf("%s",((a)?"possible":"impossible")) // The out-of-date function #define asctime(...) asctime_s(...) #define ctime(...) ctime_s(...) #define strlen(a) mystr_len(a) #define mystr_len(str) mystr_len_lim(str,9999); static char *GETWORD(char* str) {char c;char *cp;cp=&str[0];gc(c);while(c!=EOF){if((c==' ')||(c=='\n'))break;*cp++=c;gc(c);}*cp='\0';return &str[0];} static int GETLINEINT(void) {char s[34];GETLINE(s);return atoi(s);} static int GETWORDINT(void) {char s[34];GETWORD(s);return atoi(s);} static long GETWORDLONG(void) {char s[34];GETWORD(s);return atol(s);} static int maxi(int a,int b){if((a)>(b)){return a;}return b;} static long maxl(long a,long b){if(a>b){return a;}return b;} static int mystr_len_lim(char *str,int lim){int i=0;do{if(str[i]=='\0')break;i++;}while(i= 0 ) { // 親の親がある { TRACE("s%d ",saki); // 検索過程でついでにショートカットを作成しておく Friend[ parent ] = saki; // 親の親に更新 Friend[ frinum ] = saki; // 親の親に更新 TRACE("f%d=%d,",frinum,saki); frinum = parent; TRACE("p%d=%d ",parent,saki); } parent = saki; // 一つ親を注目点にする } if( saki < 0 ) { // 根を発見 frinum = parent; } Friend[ num ] = frinum; // 当人だけショートカット TRACE("ret%d\n",frinum); return frinum; } // *********************** /*! * @brief 親の番号を返す。その際とことんショートカット作成する。 * @param[in] me 本人の番号 * @param[out] nest 根までの深さを返す * @return 親の番号、居ない時は自分の番号を返す */ // *********************** int wpstack[MAXFRIEND]; int wpstackp = -1; int whoparent2( int num , int *nest) { int saki; int parent; int frinum; TRACE("\nwhoparent(%d):",num); frinum = num; *nest = 0; parent = Friend[ frinum ]; if( parent < 0 ) { TRACE("parent is none. ret%d\n",frinum); return num; // 自分が根 } wpstackp = -1; while( (saki = Friend[ parent ]) >= 0 ) { // 親の親がある wpstack[ ++wpstackp ] = parent; *nest++; parent = saki; // 一つ親を注目点にする } if( saki < 0 ) { // 根を発見 frinum = parent; } // 一部更新 int limit = 0; while( wpstackp >= 0 ) { Friend[ wpstack[ wpstackp-- ] ] = frinum; // ショートカット //if( ++limit > *nest/2 ) break; } TRACE("ret%d\n",frinum); return frinum; } // *********************** /*! * @brief 根の番号を返す * @param[in] me 本人の番号 * @return 根の番号、居ない時は自分の番号を返す */ // *********************** int whoparent3( int num ) { if( Friend[ num ] < 0 ) { return num; // 自分が根 } return Friend[ num ] = whoparent3( Friend[ num ] ); } // *********************** // 全く何もせずに親の番号を返す int whoparent4( int num ) { if( Friend[ num ] < 0 ) { return num; // 自分が根 } return whoparent4( Friend[ num ] ); } // *********************** int whoparent5( int num ) { if( Friend[ num ] < 0 ) { return num; // 自分が根 } Friend[ num ] = whoparent4( num ); // 自分だけショートカット return Friend[ num ]; } // *********************** /*! * @brief 友人リンクを作成する * @param[in] fri 友人の番号。 * @param[in] me 本人の番号 * @return 失敗したら-1を返す。 */ int addfriend( int fri, int me ) { int a_fri,b_fri; int a_pare,b_pare; TRACE("add(%d,%d) ",fri,me); if( fri == me ) return 0; // 同じ場合。 a_fri = fri; b_fri = me; a_pare = whoparent3( a_fri ); b_pare = whoparent3( b_fri ); if( a_pare > b_pare ) { SWAP(FRIENDNUMTYPE,a_pare,b_pare); // 根の若番をaにする SWAP(FRIENDNUMTYPE,a_fri,b_fri); // 根の若番をaにする } TRACE("parent(%d>%d[%d],%d>%d[%d]) ",a_fri,a_pare,Party[a_pare],b_fri,b_pare,Party[b_pare]); if( a_pare == b_pare ) { TRACE("already.\n"); return 0; // 既に友人 } else if( Party[a_pare] < Party[b_pare] ) { TRACE("set %d>%d\n",a_pare,b_pare); Friend[ a_pare ] = b_pare; Party[ b_pare ] += Party[ a_pare ]; // Party[ a_pare ] = 0; // 速度向上の為省略可 } else if( Party[a_pare] >= Party[b_pare] ){ TRACE("set %d>%d\n",b_pare,a_pare); Friend[ b_pare ] = a_pare; Party[ a_pare ] += Party[ b_pare ]; // Party[ b_pare ] = 0; // 速度向上の為省略可 } return 0; } // *********************** /*! * @brief 友人か確認する * @param[in] fri1 友人かもしれない番号。 * @param[in] fri2 本人の番号 * @return 友人なら1を返す。 */ int checkfriend( int fri1, int fri2 ) { if( whoparent3( fri1 ) == whoparent3( fri2 ) ) { return 1; } else { return 0; } } // *********************** void Init_friend( int max ) { int i; for( i = 0 ; i <= max ; i++ ) { Friend[i] = -1; Party[i] = 1; } } // ********************* // ********************* // ********************* int main( void ) { int N,M; int a,b; N = GETWORDINT(); M = GETWORDINT(); Init_friend( N ); REP1(i,M) { a = GETWORDINT(); b = GETWORDINT(); addfriend( a, b ); } TRACE("\n --- readed --- \n"); // -------- REP1(i,N) { out( whoparent3(i) ); } }