http://poj.org/problem?id=1611
水题
题意：就是找一共有多少个人感染了，0是感染学生的编号。
#include <stdio.h>
#include <string.h>
#define maxn 30005 int m,n;
int belg[ maxn ]; int Find(int x)
{
int _x=x,_b;
while( _x != belg[ _x ] )
_x = belg[ _x ];
while( x != belg[ x ] )
{
_b = belg[ x ];
belg[ x ] = _x;
x = _b;
}
return _x;
} void unio(int x,int y)
{
int root1 = Find(x);
int root2 = Find(y);
if( root1 != root2 ) belg[root2] = root1;
} int main()
{
// freopen("in.txt","r",stdin);
int a,b,c,ans;
while(scanf("%d%d",&m,&n),m||n)
{
for( int i = ; i <= m ; i++ )
belg[ i ] = i;
for( int i = ; i < n ; i++ )
{
scanf("%d%d",&a,&b);
for( int j = ; j < a- ; j++ )
{
scanf("%d",&c);
unio(b,c);
}
}
ans = ;
a = Find();
for(int i = ; i <= m ; i++ )
if(Find(i)==a) ans++;
printf("%d\n",ans);
}
return ;
}
poj 2492
http://poj.org/problem?id=2492
题意：给出m组关系，要你判断这里面有没有同性恋。
这是并查集的一个高级用法，但是我是第一次用并查集的高级用法，现在也还不是很理解这是为什么，什么意思。还得好好的模拟，想一想，感觉身体被掏空
#include <stdio.h>
#include <string.h>
#define maxn 5005 int belg[ maxn ];
bool kind[ maxn ],sign; int Find(int x, bool &s)
{
int _x, h = x;
bool s1, s2; while ( belg[h]!=h )
{
s = s^kind[h]; //这里的目的是看s也就是当前的x是不是与他的祖父是相同性别的。 h = belg[h];
} s1 = s;
while ( belg[x]!=x )
{
_x = belg[x];
belg[x] = h;
s2 = kind[x];
kind[x] = s1; //更新kind[ x ],因为最开始的x的kind就是s1，而之后的kind[ x ]就应该是s1与s2的^运算 s1 = s1^s2;
x = _x;
} return h;
} void unio(int x,int y)
{
bool su,sv;
int root1 = Find( x ,sv=false);
int root2 = Find( y ,su=false);
if( root1 == root2 ) sign = sv^su;
else {
belg[ root2 ] = root1;
kind[ root2 ] = !(su^sv);
}
} int main()
{
freopen("in.txt","r",stdin);
int t,nu = ,a,b,m,n;
scanf("%d",&t);
while(t--)
{
sign = true;
nu++;
scanf("%d%d",&m,&n);
memset( kind , false , sizeof( kind ) );
for( int i = ; i <= m ; i++ )
belg[ i ] = i;
for( int i = ; i < n ; i++ )
{
scanf("%d%d",&a,&b);
if(sign) unio(a,b);
}
printf("Scenario #%d:\n",nu);
if(sign)
printf("No suspicious bugs found!\n\n");
else
printf("Suspicious bugs found!\n\n"); }
return ;
}
poj 2498
poj 1988
http://poj.org/problem?id=1988
题意：就是给你一群盒子，有两个操作，M就是move，也就是把x盒子移到y盒子的上面。
c就是查询，查询x下面一共有多少个盒子
移动，是指x盒子及其上面的所有的盒子都一起移动到y盒子的上面去。
这个题我原来做过，那个时候不会并查集，然后就用一个结构体来记录其最下面的点，最上面的点，以及这个点下面一共有多少个盒子，然后每次维护。这样就是超时.......然后最近学了并查集，但因为对其理解还不是特别深，不是很会灵活应用，所有也不知道怎么用。最后还是看别人博客，理解别人的思路，再去自己写
思路：维护两个数组，一个是当前盒子下面一共有多少个盒子，以及自己最上面的盒子的个数。
#include <stdio.h>
#include <string.h>
#define maxn 100030 int belg[ maxn ],rank[ maxn ],top[ maxn ]; int Find(int x)
{
if(belg[x]!=x)
{
int fa = belg[x]; //每次压缩的时候，顺便更新当前点下面的合资数。
belg[x] = Find(fa);
rank[x] += rank[fa];
}
return belg[x];
} void uion(int x,int y)
{
int root1 = Find( x );
int root2 = Find( y );
if( root1 != root2 )
{
belg[ root1 ] = root2; //把x移到y的上面，以及更新x的下面的数量和y最上面的的数量。
rank[ root1 ] = top[ root2 ] + ;
top[ root2 ] += top[ root1 ]+;
} } int main()
{
// freopen("in.txt","r",stdin);
int t,a,b;
char x;
scanf("%d",&t);
for(int i = ; i <= t ; i++)
belg[ i ] = i;
while(t--)
{
scanf("%s",&x);
if(x=='M')
{
scanf("%d%d",&a,&b);
uion( a , b );
}
else
{
scanf("%d",&a);
Find( a );
printf("%d\n",rank[ a ] );
}
}
return ;
}
poj 1988
poj 2912
http://poj.org/problem?id=2912
题意：有n个人在玩石头剪刀布，这其中就有一个是裁判，而且每一个人都只会出一种手势，要你求是否可以判断出裁判是哪个，并且输出在第几个语句可以判断。
这个题有点像那个食物链的题目，我在判断语句时，也是采取了和食物链一样的写法。
思路：就是枚举每一个人当为裁判，然后进行判断，看看其他与这个裁判无关的语句，是否有矛盾，如果没有矛盾，说明这个人有可能是裁判，如果有，那么这个人就肯定不能当裁判，最后如果没有符合条件的，就输出impossible，如果超过了一个人就输出Can not determine，如果恰好是一个人就输出可以找到，并且把裁判和在哪个语句中可以判断出，在哪个语句中可以判断出的话，这个就是在看最后一个产生矛盾的语句是在哪产生的，因为但枚举的不是这个裁判的时候，这个裁判的语句就会被合并，当找到最后一个矛盾产生的语句时，也就可以判断这个裁判是在哪里被找出来的了。
关于那些语句看不懂可以先去看看我写的食物链。Poj 1182
http://www.cnblogs.com/Tree-dream/p/5709880.html
#include <stdio.h>
#include <string.h>
#define maxn 2005 struct note{
int x,mark,y;
}s[ maxn ]; int m,n,belg[ maxn * ];
bool mark[ maxn * ]; int Find(int x)
{
int _x=x,_b;
while(_x!=belg[_x])
{
_x=belg[_x];
}
while(x!=belg[x])
{
_b=belg[x];
belg[x]=_x;
x=_b;
}
return _x;
} bool judge(int x,int y) {
if(Find(x)==Find(y))
return true;
else return false;
} void unite(int x,int y)
{
int root1=Find(x);
int root2=Find(y);
if(root1!=root2) belg[root1]=root2;
} void init()
{
for( int i = ; i <= *m ; i++ )
belg[ i ] = i;
} int main()
{
// freopen("in.txt","r",stdin);
int a,b;
char c;
while(scanf("%d%d",&m,&n)!=EOF)
{
init();
for(int i = ; i <= n ; i++ )
{
scanf("%d%c%d",&a,&c,&b);
getchar();
if(c=='=')
{
s[ i ].x = a;
s[ i ].y = b;
s[ i ].mark = ;
}
if(c=='<')
{
s[ i ].x = b;
s[ i ].y = a;
s[ i ].mark = ;
}
if(c=='>')
{
s[ i ].x = a;
s[ i ].y = b;
s[ i ].mark = ;
}
}
int i,sign = ,falg = ,y = ,j;
for( i = ; i < m ; i++ )
{
init();
for(j = ;j <= n ; j++ )
{
if(s[ j ].x != i && s[ j ].y != i)
{
if(s[ j ].mark == )
{
if(judge(s[ j ].x,s[ j ].y + m )||judge(s[ j ].x,s[ j ].y + * m))
{
if( j > y ) y = j;
break;
}
else
{
unite(s[ j ].x , s[ j ].y);
unite(s[ j ].x + m , s[ j ].y + m);
unite(s[ j ].x + * m , s[ j ].y + * m);
}
}
else
{
if(judge( s[ j ].x , s[ j ].y)||judge(s[ j ].x , s[ j ].y + * m))
{ if( j > y ) y = j;
break;
}
else
{
unite( s[ j ].x , s[ j ].y + m );
unite( s[ j ].x + m , s[ j ].y + * m );
unite( s[ j ].x + * m , s[ j ].y );
}
}
}
}
if(j == n+)
{
falg ++;
sign = i;
}
}
if(falg == ) printf("Impossible\n");
else if(falg > ) printf("Can not determine\n");
else printf("Player %d can be determined to be the judge after %d lines\n",sign,y); }
return ;
}
poj 2912
HDU 3038
题意：n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的。
思路：并查集，维护一个之间和的序列就可以。
#include <stdio.h>
#include <string.h>
#define maxn 200020 int belg[ maxn ],sum[ maxn ]; int Find(int x)
{
if(x!=belg[x])
{
int fa = belg[ x ];
belg[ x ] = Find(fa);
sum[ x ] += sum[ fa ];
}
return belg[ x ];
} int main()
{
// freopen("in.txt","r",stdin);
int m,n,a,b,c; while(scanf("%d%d",&m,&n)!=EOF)
{
int ans=;
for( int i = ; i <= m ; i++ )
belg[ i ] = i,sum[ i ] = ;
for( int i = ; i < n ; i++ )
{
scanf("%d%d%d",&a,&b,&c);
b--; //这里记得--
int root1 = Find(a),root2 = Find(b);
if(root1 == root2)
{
if(sum[ b ]-sum[ a ] != c) ans++;
}
else
{
belg[ root2 ] = root1;
sum[ root2 ] = sum[ a ]- sum[ b ] + c;
}
}
printf("%d\n",ans);
}
return ;
}
hdu 3038